很难的一道$dp$，考场上我只得了$10$分。。其实如果做过这道题对于状态的设计就会有所感觉
设$dp[i][j]$表示到$i$点还剩$j$的距离可以去用，也就是说如果$j$等于0时，就只能严格按最短路走到$n$，否则可以沿着其他路走，但不能让$j$走成0
首先跑一遍最短路，求出一号店到其他点的距离，然后建反图跑。这样就有$70$分。至于零环的处理我们可以这样想，假如我们花费$k$的费用到达$i$号点，再从该店往外走，当我们到达另一个点且仍花费$k$时，如果该点到$i$号点有边且费用为0，那么这中间就形成了一个零环
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #define M 200010 6 using namespace std; 7 int read() 8 { 9 char ch=getchar();int x=0; 10 while(ch>‘9‘||ch<‘0‘) ch=getchar(); 11 while(ch<=‘9‘&&ch>=‘0‘) x=x*10+ch-‘0‘,ch=getchar(); 12 return x; 13 } 14 int n,m,k,mod,num; 15 int head[M],dis[M],lft[M],dp[M][60],a[M],b[M],c[M]; 16 bool flag,vis[M],in[M]; 17 struct point{int to,next,dis;}e[M<<1]; 18 void add(int u,int v,int dis) {e[++num].next=head[u];e[num].to=v;e[num].dis=dis;head[u]=num;} 19 void SPFA() 20 { 21 queue<int>q;q.push(1); 22 memset(dis,0x3f,sizeof(dis)); 23 vis[1]=true; dis[1]=0; 24 while(!q.empty()) 25 { 26 int x=q.front();q.pop(); 27 for(int i=head[x];i;i=e[i].next) 28 { 29 int to=e[i].to; 30 if(dis[to]>dis[x]+e[i].dis) 31 { 32 dis[to]=dis[x]+e[i].dis; 33 if(!vis[to]) 34 { 35 q.push(to); 36 vis[to]=true; 37 } 38 } 39 } 40 vis[x]=false; 41 } 42 } 43 int DFS(int x,int left) 44 { 45 if(~dp[x][left]) return dp[x][left]; 46 dp[x][left]=(x==1); 47 for(int i=head[x];i;i=e[i].next) 48 { 49 int to=e[i].to; 50 int k=left-(dis[to]+e[i].dis-dis[x]); 51 if(k<0) continue; 52 if(in[to]&&lft[to]==k) flag=true; 53 else in[to]=true,lft[to]=k; 54 dp[x][left]=(dp[x][left]+DFS(to,k))%mod; 55 in[to]=false;lft[to]=0; 56 } 57 return dp[x][left]; 58 } 59 void work() 60 { 61 memset(head,0,sizeof(head)); num=0; 62 n=read();m=read();k=read();mod=read(); 63 for(int i=1;i<=m;i++) 64 { 65 a[i]=read(),b[i]=read(),c[i]=read(); 66 add(a[i],b[i],c[i]); 67 } 68 SPFA(); 69 memset(head,0,sizeof(head));num=0; 70 for(int i=1;i<=m;i++) add(b[i],a[i],c[i]); 71 memset(dp,-1,sizeof(dp)); memset(lft,0,sizeof(lft)); 72 memset(in,0,sizeof(in)); flag=false; 73 DFS(n,k); 74 printf("%d\n",flag?-1:DFS(n,k)); 75 } 76 int main() 77 { 78 int T=read(); 79 while(T--) work(); 80 return 0; 81 }
原文：https://www.cnblogs.com/Slrslr/p/9606550.html