正解:图论(最短路)+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就卡着时间过辣!