问题

从1到5一共有几条最短路？

思考

我们思考一下上一篇的代码，发现

for(i=head[now];i!=-1;i=vec[i].nex) { if(dis[vec[i].v] > dis[now] + vec[i].w) { dis[vec[i].v] = dis[now] + vec[i].w; q.push(make_pair(dis[vec[i].v],vec[i].v)); } }

这里只是找到比其小的路径就覆盖并且放入队列中，那要是等于的话呢？

结论

我们用一个数组去记录每一个点的前驱，(例如vec[i].v 的前驱为now)。碰到更小的点那么就全部覆盖并更新为最小的点。如果碰到路径一样的点那就在后面添加这个now

根据上图得出的结果如下

ans = 8 1 : 2 : 1 3 : 1 4 : 2 3 5 : 3 4

光看最后一行，其意义为：1(起始点)到3由3再到5是一条最短路径，1(起始点)到4由4再到5也是一条最短路径。上面同理，有了个数组我们用一个dfs就可以将所有的路全部找出来了。

具体代码如下：

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #define F1(i,n) for(i=1;i<=n;i++) #define F0(i,n) for(i=0;i<=n;i++) #define _F1(i,n) for(i=n;i>=1;i--) #define _F0(i,n) for(i=n;i>=0;i--) #define INF 0x7f7f7f7f using namespace std; struct node { int u,v,w,nex; }; int head[600]; int n,m,k; int dis[600]; bool vis[600]; bool visit[600];//dfs*用 vector <node> vec; vector <int> path[600]; vector <int> ans; int cnt; priority_queue <pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q; void addEdge(int x,int y,int z) { vec.push_back({x,y,z,head[x]}); head[x] = vec.size() - 1; } void dijkstra(int pos) { for(int i=1;i<=n;i++)dis[i] = INF; dis[pos] = 0; q.push({0,pos}); while(!q.empty()) { int now = q.top().second; q.pop(); if(vis[now])continue; vis[now] = 1; for(int i=head[now];i!=-1;i=vec[i].nex) { if(dis[vec[i].v] > dis[now] + vec[i].w) { dis[vec[i].v] = dis[now] + vec[i].w; path[vec[i].v].clear(); path[vec[i].v].push_back(now); q.push({dis[vec[i].v],vec[i].v}); continue; } if(dis[vec[i].v] == dis[now] + vec[i].w) { path[vec[i].v].push_back(now); q.push({dis[vec[i].v],vec[i].v}); } } } } void dfs2(int pos) { int i,j; /* 本dfs是寻找所有最短路径(如果两条路径有一条边相同，就认为相同) */ for(i=0;i<path[pos].size();i++) { if(!visit[path[pos][i]]) { ans.push_back(path[pos][i]); if(path[pos][i] == 1)//这里的1就是起点 { cnt++; //cout<<"the"<<cnt<<" : "; //for(j=ans.size()-1;j>=0;j--)cout<<ans[j]<<" "; //cout<<endl; } if(path[pos][i] != 1) visit[path[pos][i]] = 1; dfs2(path[pos][i]); //visit[path[pos][i]] = 0; i ra na i ans.pop_back(); } } } void dfs1(int pos) { /* 本dfs是寻找所有最短路径(如果两条路径有一条边不相同，就认为这两条路径不同) */ int i,j; for(i=0;i<path[pos].size();i++) { ans.push_back(path[pos][i]); if(path[pos][i] == 1) { cnt++; //cout<<"the"<<cnt<<" : "; //for(j=ans.size()-1;j>=0;j--)cout<<ans[j]<<" "; //cout<<endl; } int tmp = path[pos][i]; //dfs(path[pos][i]); dfs1(tmp); ans.pop_back(); } } int main() { register int i,j; int T; freopen("in","r",stdin); scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&k); vec.clear(); ans.clear(); cnt = 0;//最短路数量 for(i=1;i<=n;i++)path[i].clear(); while(!q.empty())q.pop(); vec.push_back({0,0,0,-1}); memset(head,-1,sizeof(head)); memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(visit,0,sizeof(visit)); F1(i,m) { int x,y,z; cin>>x>>y>>z; addEdge(x,y,z); } dijkstra(1); if(dis[n] == 0x7f7f7f7f)//不存在到n的最短路 { cout<<-1<<endl<<-1<<endl; continue; } /* 这里是dijkstra后path的结果，用dfs*去求路径个数即可 cout<<"ans = "<<dis[n]<<endl; for(i=1;i<=n;i++) { cout<<i<<" : "; for(j=0;j<path[i].size();j++) { cout<<path[i][j]<<" "; } cout<<endl; } */ ans.push_back(n); dfs1(n); cout<<cnt<<endl; cnt = 0; dfs2(n); cout<<cnt<<endl; } return 0; }

后记

想通了很简单吧。