本文共 3091 字，大约阅读时间需要 10 分钟。
和天梯中的直捣黄龙差不多。但是，通过这个问题，我对多参数最短路又有了更深一层的了解。
这题因为点数比较多，所以如果直接用大力学长的在G上dfs找最短路径的条数的话，会TLE，所以需要剪枝。剪枝方法是，在dfs中当遇到dis>d[u]就直接return。具体见代码：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 using namespace std; 13 const int inf = 0x3f3f3f3f; 14 typedef long long ll; 15 typedef pair pii; 16 const int N = 500 + 5; 17 18 int n,m,st,ed; 19 int d[N],d2[N],val[N],pre[N]; 20 struct edge 21 { 22 int v,w; 23 }; 24 vector G[N]; 25 26 void dij() 27 { 28 memset(pre,-1,sizeof(pre)); 29 memset(d,inf,sizeof(d)); 30 memset(d2,0,sizeof(d2)); 31 d[0]=0; 32 d2[0]=val[0]; 33 priority_queue ,greater > Q; 34 Q.push(pii(0,0)); 35 while(!Q.empty()) 36 { 37 pii x = Q.top();Q.pop(); 38 int u = x.second; 39 int dis = x.first; 40 if(d[u] = d[u]+e.w) 45 { 46 if(d[e.v] > d[u]+e.w) 47 { 48 pre[e.v] = u; 49 d[e.v] = d[u]+e.w; 50 d2[e.v] = d2[u]+val[e.v]; 51 Q.push(pii(d[e.v],e.v)); 52 } 53 else 54 { 55 if(d2[e.v] < d2[u]+val[e.v]) 56 { 57 pre[e.v] = u; 58 d2[e.v] = d2[u]+val[e.v]; 59 Q.push(pii(d[e.v],e.v)); 60 } 61 } 62 } 63 } 64 } 65 } 66 67 int cnt = 0; 68 bool vis[N]; 69 void dfs(int u,int dis) 70 { 71 if(u==ed && dis==d[ed]) {cnt++;return;} 72 if(dis > d[ed]) return; // 剪枝！ 73 for(int i=0;i
当然，用我自己之前的方法也是可以的：用set型的p数组记录来时的点，再反向dfs即可。具体见代码：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 using namespace std; 13 const int inf = 0x3f3f3f3f; 14 typedef long long ll; 15 typedef pair pii; 16 const int N = 500 + 5; 17 18 int n,m,st,ed; 19 int d[N],d2[N],val[N],pre[N]; 20 set p[N]; 21 struct edge 22 { 23 int v,w; 24 }; 25 vector G[N]; 26 27 void dij() 28 { 29 memset(pre,-1,sizeof(pre)); 30 memset(d,inf,sizeof(d)); 31 memset(d2,0,sizeof(d2)); 32 d[0]=0; 33 d2[0]=val[0]; 34 priority_queue ,greater > Q; 35 Q.push(pii(0,0)); 36 while(!Q.empty()) 37 { 38 pii x = Q.top();Q.pop(); 39 int u = x.second; 40 int dis = x.first; 41 if(d[u] = d[u]+e.w) 46 { 47 if(d[e.v] > d[u]+e.w) 48 { 49 p[e.v].clear(); 50 p[e.v].insert(u); 51 52 pre[e.v] = u; 53 d[e.v] = d[u]+e.w; 54 d2[e.v] = d2[u]+val[e.v]; 55 Q.push(pii(d[e.v],e.v)); 56 } 57 else 58 { 59 p[e.v].insert(u); 60 61 if(d2[e.v] < d2[u]+val[e.v]) 62 { 63 pre[e.v] = u; 64 d2[e.v] = d2[u]+val[e.v]; 65 Q.push(pii(d[e.v],e.v)); 66 } 67 } 68 } 69 } 70 } 71 } 72 73 int cnt = 0; 74 void dfs(int u) 75 { 76 if(u == st) {cnt++;return;} 77 for(set ::iterator it=p[u].begin();it!=p[u].end();it++) 78 { 79 int v = *it; 80 dfs(v); 81 } 82 } 83 84 void printAns(int now) 85 { 86 if(now != st) {printAns(pre[now]);printf(" ");} 87 printf("%d",now); 88 } 89 90 int main() 91 { 92 while(scanf("%d%d%d%d",&n,&m,&st,&ed)==4) 93 { 94 for(int i=0;i
想说明一点的是，我的方法跑的比大力学长的跑的快了2ms：他的46，我的44。。233= =。
转载于:https://www.cnblogs.com/zzyDS/p/5681364.html
