題目鏈接

好久沒敲?迪杰斯特拉算法了，這個模板題目搞一波。

#include <iostream> #include <queue> #include <cstring> #include <vector> #include <algorithm> #include <cstdio> #define Heap pair<int,int> using namespace std; priority_queue< Heap,vector<Heap>,greater<Heap> > s; const int MAXN=20005; struct node{int u,v,w,next;node() {}node(int _u,int _v,int _w,int _next){u = _u,v = _v, w = _w,next = _next;} }G[MAXN]; int n,m,start,end,Count,head[MAXN],dis[MAXN];void AddEdge(int u,int v,int w){G[Count] = node(u,v,w,head[u]);head[u] = Count++; }void Dij(int x){for(int i=1;i<=n;i++) dis[i]=999999999;dis[x] = 0;s.push(make_pair(dis[x],x));while( !s.empty() ){Heap N = s.top();s.pop();int fuck = N.second;if(dis[fuck]!=N.first) continue;for(int e = head[fuck];e != -1;e=G[e].next){int v =G[e].v;int w =G[e].w;if(dis[fuck]+w<dis[v]){dis[v] = dis [fuck] + w;s.push(make_pair(dis[v],v));}}}printf("%d\n",dis[end]);return; }int main(){memset(head,-1,sizeof(head));scanf("%d%d%d%d",&n,&m,&start,&end);for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);AddEdge(x,y,z);AddEdge(y,x,z);} Dij(start);return 0; } 地杰斯特拉算法

?

轉載于:https://www.cnblogs.com/OIerLYF/p/6944244.html

總結

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

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