正解:图论(最短路)+dp(记忆化搜索)
解题报告:
这题真的是个好东西!
做了这题我才发现我的dij一直是错的...但是我以前用dij做的题居然都A了?什么玄学事件啊...我哭了TT
不过其实感觉还挺幸运的,好歹是考前发现?不然考完才知道就GG了...
先正儿八经讲完解法再吐槽自己...
先dij跑一遍最短路
然后再走一遍,我们可以跑到d+k相当于我们可以浪费k
然后dp[i][j]表示跑到第i个点了还可以浪费j的方案数
最后Σdp[n][1~k]就欧克辽...
就是个记忆化搜索
对了了解到好像说自古D1有一dp?那如果按照去年套路来说T1数论T2大模拟T3就多往dp上想?这题的话就记忆化搜索嘛也是dp对趴qwq
哦然后关于转移,这个大概是唯一难点?
写一下关键好了 理解一下,从u到v我们强制要求跑uv边,那转移造成的的浪费就是
dis[v]+w[edge(u,v)]-dis[u]
就还能浪费 lf-(上面那坨)
然后初始状态是跑到了f[n][0]的时候f[n][0]=1
over
然后贴下代码:
#include<bits/stdc++.h>
using namespace std;
#define rp(i,x,y) for(register int i=x;i<=y;++i)
#define pr pair<int,int>
#define mp make_pair
,M=;
],T;
long long ans;
struct ed{int to,next,wei;}edge1[M],edge2[M];
],flg;
priority_queue< pr , vector<pr> , greater<pr> >Q;
inline int read()
{
;;
'))ch=getchar();
if(ch=='-')ch=getchar();
)+(x<<)+(ch^'),ch=getchar();
return y?x:-x;
}
inline void pre()
{
memset(vis,,/,,,sizeof(head2));
memset(instack,,,;ans=;flg=;memset(edge1,,,sizeof(edge2));
}
inline void add1(int x,int y,int z){edge1[++tot].to=y;edge1[tot].next=head1[x];edge1[tot].wei=z;head1[x]=tot;}
inline void add2(int x,int y,int z){edge2[tot].to=y;edge2[tot].next=head2[x];edge2[tot].wei=z;head2[x]=tot;}
inline void dij()
{
Q.push(mp(,n));dis[n]=;
while(!Q.empty())
{
int t=Q.top().second;Q.pop();
)continue;
vis[t]=;
;i=edge2[i].next)
if(dis[edge2[i].to]>dis[t]+edge2[i].wei){dis[edge2[i].to]=dis[t]+edge2[i].wei;Q.push(mp(dis[t]+edge2[i].wei,edge2[i].to));}
}
}
int dfs(int u,int lf)
{
,;;;
;i=edge1[i].next)
{ && temp<=cjk)goldgenius=(goldgenius+dfs(edge1[i].to,temp))%mod;;}
)goldgenius=;instack[u][lf]=;
return f[u][lf]=goldgenius;
}
int main()
{
// freopen("cjk.in","r",stdin);
// freopen("cjk.out","w",stdout);
T=read();
while(T--)
{
pre();n=read();m=read();cjk=read();mod=read();
rp(i,,m){int t1=read(),t2=read(),t3=read();add1(t1,t2,t3);add2(t2,t1,t3);}
dij();
rp(i,,cjk){memset(instack,,,i))%mod;}
flg?printf("-1\n"):printf("%lld\n",ans);
}
;
}
QAQ
吐槽:
苍了天了...港真我真的很震惊了,毕竟图论的题我也做了不少了一直打得是错的为什么都A了?题目也太水了点趴都???我真的???
然后港下我哪儿错了,就是优先队列是不能更改那个值的趴好像,所以你直接修改不会使得顺序改变所以其实是错的....ummm..所以为什么我之前对了呢...
然后贴下真正正确的代码...
inline void dij()
{
Q.push(mp(,n));dis[n]=;
while(!Q.empty())
{
int t=Q.top().second;Q.pop();
if(vis[t])continue;
vis[t]=;
;i=edge2[i].next)
if(dis[edge2[i].to]>dis[t]+edge2[i].wei){dis[edge2[i].to]=dis[t]+edge2[i].wei;Q.push(mp(dis[t]+edge2[i].wei,edge2[i].to));}
}
}
!!
a还有个玄学操作?就是我发现我之前A的代码有个判断好像错了?我就删了?然后就成功T了一个点???
是这样的:
if(vis[t] && t-1)continue;
然后我改成这样,就会T:
if(vis[t])continue;
我又改成这样,还是T:
if(vis[t] && t!=1)continue;
我就很懵,于是改成这样,依然是T的:
if(vis[t] && t-1!=0)continue;
这是什么玄学啊...哭了.不知道是常数太大还是怎么?
哦但是我写spfa一发过...也是清奇x
upd:11.9 写完最短路模板实在不服气于是我就就就又去做了下...然后加一堆register就卡着时间过辣!