題意：給你n個點的有向圖，從1點到其他所有點又從其他點回到1點的最短路。

?

思路：可以求一次從1點出發的最短路，再反向建圖，再求一次從1出發的最短路，把兩次的結果加起來就是題目所求。由于邊比較多，

? 所以最好用Dijkstra+優先隊列，或者SPFA；

?

?

#include<cstdio> #include<cstring> #include<queue> #include<algorithm> const int maxn = 1000009; const int inf = 1<<30; #include<vector> struct node {int v,w;node(int v,int w):v(v),w(w){}bool operator < (const node a)const{return w > a.w;} }; std::vector<node> eg[maxn]; std::priority_queue<node> q; int n,m; int vis[maxn]; int dis[maxn]; int a[maxn],b[maxn],c[maxn];void DIJ() {int i;memset(vis,0,sizeof(vis));for(i=0;i<=n;i++)dis[i] = inf;while(!q.empty())q.pop();dis[1] = 0;vis[1] = 0;int size = eg[1].size();for(i=0; i < size; i++){q.push(node(eg[1][i].v,eg[1][i].w));dis[eg[1][i].v] = eg[1][i].w;}while(!q.empty()){int u = q.top().v;int w = q.top().w;q.pop();if(!vis[u]){vis[u] = 1;size = eg[u].size();for(i=0; i<size; i++){int v = eg[u][i].v;int w = eg[u][i].w;if(!vis[v] && dis[u] + w < dis[v]){dis[v] = dis[u] + w;q.push(node(v,dis[v]));}}}}} void work() {int i,sum = 0;DIJ();for(i=2; i<=n; i++) sum += dis[i]; //printf("%d ",dis[i]);}for(i=0; i<=n; i++) eg[i].clear();for(i=0;i<m;i++) eg[b[i]].push_back(node(a[i],c[i]));// printf("\n");DIJ();for(i=2; i <= n;i++) sum += dis[i]; //printf("%d ",dis[i]);}printf("%d\n",sum); } void input() {int i;scanf("%d%d",&n,&m);for(i=0 ;i < m; i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);for(i=0;i<=n;i++) eg[i].clear();for(i=0;i<m;i++) eg[a[i]].push_back(node(b[i],c[i])); } int main() {int t;scanf("%d",&t);while(t--){input(); work();}return 0; }/*3 2 2 1 2 13 2 1 33 4 6 1 2 10 2 1 60 1 3 20 3 4 10 2 4 5 4 1 50 2 2 1 2 13 2 1 33*/

?

轉載于:https://www.cnblogs.com/BruceNoOne/p/3900518.html

總結

以上是生活随笔為你收集整理的zoj2008 最短路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。