可以先建图（正反都要），跑一遍最短路，在枚举 0−k0-k0−k ，因为 kkk 比较小枚举按道理是不会超时的，除非时你写错了，跑一遍反图，所有的情况求和，就好了 可是怎么求答案呢： 可以 dpdpdp 来做，用 fff [ iii ][ jjj ]表示从 nnn 到 iii 的距离 <<< 最短距离 +k+k+k 的方案数，对于每一条边都尝试走，而这个状态可以表示为 u−>vu->vu−>v : ddd [ uuu ] −d-d−d [ vvv ] +k−len+k-len+k−len [ u−>vu->vu−>v ];

#include <cstdio> #include <queue> #include <vector> #include <cstring> using namespace std; int t,d[100001],f[100001][51],n,m,k,p; bool working[100001][51]; struct node { int to,len; }; vector<node>head[100001]; vector<node>h[100001]; //这里用两个vector来存图，初始化的时候非常方便 //，强烈建议使用，不容易出错 int dp(int root, int l){ //这才是这道题的奥妙所在 //root表示到哪个点了，l表当前的k还有多少剩余 int ans=0; //反向跑是因为可以减少跑死胡同的情况增加效率， //一些不能到达n的路径就可以不用跑了，可以自行画图理解 if (l<0||l> k) return 0;//这种情况说明答案不合法 if (working[root][l]) { //working数组是为了判断‘0’环的情况， //当其已经为1时代表它已经跑过了，就可以跳出来了 working[root][l]=false; return -1; } if(f[root][l]!=-1) //f有值了代表求出答案了 return f[root][l]; working[root][l]=true; for (int i=0;i<h[root].size();i++) {//跑反图 node e= h[root][i]; int val=dp(e.to,d[root]+l-d[e.to]-e.len); //这个表达式，表示用尝试当前这条边替换其中最短路径里的一条边 //来求一个合法的解 if (val==-1) { working[root][l]=false; return -1; } ans=(ans+val)%p; } working[root][l] = false; if (root1&&l0) ans++; //跑到这里是证明这是一个解ans就+1 f[root][l]=ans;//记录答案 return ans; } int work(){ scanf("%d%d%d%d", &n, &m, &k, &p); for (int i=1;i<=n;i++) {//看，初始化只要几行就好了 head[i].clear(); h[i].clear(); } int a, b, c; for (int i=1;i<= m;i++) {//存图 scanf("%d%d%d",&a,&b,&c); node e; e.to=b; e.len=c; head[a].push_back(e); e.to=a; //反图 h[b].push_back(e); } memset(d,0x3f,sizeof(d)); //spfa memset(f,-1,sizeof(f)); //记得初始化，否则会wa声一片 queue<int>q; q.push(1); d[1]=0; while (!q.empty()) { int x=q.front(); q.pop(); for (int i=0;i<head[x].size();i++) { if (d[head[x][i].to]>d[x]+head[x][i].len) { d[head[x][i].to]=d[x]+head[x][i].len; q.push(head[x][i].to); } } } int ans=0; for (int i=0;i<=k;i++) { //dp 枚举k：0-k, int val=dp(n,i); //求和后就是答案 if (val==-1) return -1; ans=(ans+val)%p; } return ans; } int main(){ scanf("%d", &t); while(t--) printf("%d\n", work()); return 0; }