題意：

有N個點，給出從a點到b點的距離，當然a和b是互相可以抵達的，問從1到n的最短距離

分析：

典型的模板題，但是一定要注意有重邊，因此需要對輸入數據加以判斷，保存較短的邊，這樣才能正確使用模板。

題解

#include<iostream> #include<Queue> #include<cstdio> #include<vector> #include<string.h> using namespace std; #define maxn 2001 #define inf 0x3f3f3f int map[maxn][maxn]; int dist[maxn]; bool visited[maxn]; typedef pair<int,int> P; void dijkstra(int s,int n){priority_queue<P,vector<P>,greater<P> > Q;memset(visited,0,sizeof(visited));for(int i=1;i<=n;i++){dist[i]=inf;}dist[s]=0;Q.push(P(0,s));while(!Q.empty()){ int v=Q.top().second;Q.pop();if(visited[v]) continue;visited[v]=true;for(int i=1;i<=n;i++){int len=dist[v]+map[v][i];if(dist[i]>len){dist[i]=len;Q.push(P(len,i));}}} } int main(){int n,t;while(scanf("%d %d",&t,&n)!=EOF){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){map[i][j]=(i==j?0:inf);}}while(t--){int b,c,d;scanf("%d %d %d",&b,&c,&d);if(map[b][c]>d){map[b][c]=d;map[c][b]=d;}}dijkstra(n,n);printf("%d\n",dist[1]);} }

轉載于:https://www.cnblogs.com/ZJUT-jiangnan/p/3934516.html

總結

以上是生活随笔為你收集整理的POJ - Til the Cows Come Home(Dijkstra)的全部內容，希望文章能夠幫你解決所遇到的問題。

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