\u5bb9\u6613\u77e5\u9053\uff0c\u5bf9\u4e8e\u6bcf\u4e2a\u70b9\uff0c\u6700\u591a\u53ea\u80fd\u504f\u79fb50\u3002
\n\u7531\u6b64\u53ef\u4ee5\u8dd1\u8bb0\u5fc6\u5316\u641c\u7d22\uff1a\\(f_{i,j}\\)\u8868\u793a\uff0c\u5728\u7b2ci\u4e2a\u70b9\uff0c\u6bd4\u6700\u77ed\u8def\u957f\u4e86j\u65f6\u7684\u65b9\u6848\u6570\u3002
\n\u90a3\u4e48\uff0c\u6211\u4eec\u5012\u7740\u641c\u5373\u53ef\u3002
\n\u5177\u4f53\u6765\u8bf4\uff0c\u5b9a\u4e49\\(dn_{x}\\)\u8868\u793a\\(x->u\\)\u7684\u6700\u77ed\u8def\u3002
\n\u90a3\u4e48\u6211\u4eec\u53ef\u4ee5\u5f97\u5230\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\uff1a
\n$$f_{u,k}=\\sum_{v,v\\in S,st: \\forall x \\in S,x_{u}=u}f_{v,k-dn_{v}+dn_{u}-w}$$
\n\u7b54\u6848\u4e3a\\(f_{1,K}\\)
\n\u51e0\u4e2a\u7ec6\u8282\uff1a
\ne[i].nxt\u4e0d\u5e94\u5199\u4f5ce[i].v
\n\u4e0d\u8981\u4f7f\u7528\u957f\u5f97\u5dee\u4e0d\u591a\u7684\u53d8\u91cf\u3002<\/p>\n
#include<iostream>\r\n#include<cstdio>\r\n#include<queue> \r\n#include<cstring>\r\nusing namespace std;\r\nstruct ee{\r\n int v;\r\n int w;\r\n int nxt;\r\n}e[400005];\r\nint h[100005],h2[100005],et=0,n,m,K,p,dis[100005],dn[100005],f[100005][51];\r\nbool usd[100005][51];\r\ninline void add(int *_H,const int &u,const int &v,const int &w){\r\n e[++et]=(ee){v,w,_H[u]};\r\n _H[u]=et;\r\n}\r\nstruct cmp2{\r\n inline bool operator ()(const int &X,const int &Y)const{\r\n return dn[X]>dn[Y];\r\n }\r\n};\r\nvoid dij2(){\r\n priority_queue< int,vector<int>,cmp2 > q;\r\n memset(dn,0x3f,sizeof(dn));\r\n dn[n]=0;\r\n q.push(n);\r\n int nw;\r\n while(!q.empty()){\r\n nw=q.top();\r\n q.pop();\r\n for(int i=h2[nw];i;i=e[i].nxt){\r\n if(dn[e[i].v]>dn[nw]+e[i].w){\r\n dn[e[i].v]=dn[nw]+e[i].w;\r\n q.push(e[i].v);\r\n }\r\n }\r\n }\r\n}\r\nint dfs(int u,int k){\r\n if(usd[u][k]){\r\n return -1;\r\n }\r\n if(f[u][k]){\r\n return f[u][k];\r\n }\r\n usd[u][k]=1;\r\n if(u==n){\r\n f[u][k]=1;\r\n }\r\n int X,sm;\r\n for(int i=h[u];i;i=e[i].nxt){\r\n \/\/e[i].v\u4e0d\u80fd\u5199\u6210e[i].nxt \r\n sm=dn[e[i].v]-dn[u]+e[i].w;\r\n if(sm>k){\r\n continue;\r\n }\r\n X=dfs(e[i].v,k-sm);\r\n if(X==-1){\r\n return f[u][k]=-1;\r\n }\r\n f[u][k]+=X;\r\n f[u][k]%=p;\r\n }\r\n usd[u][k]=0;\r\n return f[u][k];\r\n}\r\nvoid init(){\r\n memset(h,0,sizeof(h));\r\n memset(h2,0,sizeof(h2));\r\n scanf(\"%d%d%d%d\",&n,&m,&K,&p);\r\n et=0;\r\n int u,v,w;\r\n for(int i=1;i<=m;++i){\r\n scanf(\"%d%d%d\",&u,&v,&w);\r\n add(h,u,v,w);\r\n add(h2,v,u,w);\r\n }\r\n dij2();\r\n memset(f,0,sizeof(f));\r\n memset(usd,0,sizeof(usd));\r\n printf(\"%d\\n\",dfs(1,K));\r\n}\r\nint main(){\r\n int T;\r\n scanf(\"%d\",&T);\r\n while(T--){\r\n init();\r\n }\r\n return 0;\r\n}<\/code><\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
\u5bb9\u6613\u77e5\u9053\uff0c\u5bf9\u4e8e\u6bcf\u4e2a\u70b9\uff0c\u6700\u591a\u53ea\u80fd\u504f\u79fb50\u3002 \u7531\u6b64\u53ef\u4ee5\u8dd1\u8bb0\u5fc6\u5316\u641c\u7d22\uff1a\\(f_{i,j}\\)\u8868\u793a\uff0c\u5728\u7b2ci\u4e2a\u70b9\uff0c\u6bd4\u6700\u77ed … <\/p>\n