題目:http://acm.nefu.edu.cn/JudgeOnline/problemshow.php?problem_id=208

#include <iostream> #include <string.h> #include <stdio.h>using namespace std; const int N = 1005; const int INF = 1<<30;int map[N][N]; int dist[N]; bool vis[N]; int n,m;void Init() {memset(vis,0,sizeof(vis));for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)map[i][j] = INF; }void Dijkstra(int cur) {vis[cur] = 1;for(int i=1; i<=n; i++)dist[i] = map[cur][i];dist[cur] = 0;for(int i=2; i<=n; i++){int k = cur;int minval = INF;for(int j=1; j<=n; j++){if(!vis[j] && dist[j] < minval){minval = dist[j];k = j;}}vis[k] = 1;for(int j=1; j<=n; j++){if(!vis[j])dist[j] = min(dist[j],dist[k] + map[k][j]);}} }int main() {while(~scanf("%d%d",&n,&m)){Init();for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);u++; v++;map[u][v] = w;}int s,t;scanf("%d%d",&s,&t);s++; t++;Dijkstra(s);if(dist[t] == INF) puts("-1");else printf("%d\n",dist[t]);}return 0; }

Dijkstra經過set優化后，時間復雜度可以將為O(n*log(n))

#include <iostream> #include <string.h> #include <stdio.h> #include <set>using namespace std; const int N = 1005; const int INF = 1 << 30;struct Edge {int to;int w;int next; };Edge edge[N*N]; int head[N],dist[N]; bool vis[N]; int cnt;struct cmp {bool operator()(const int &a,const int &b) const{return dist[a] < dist[b] || (dist[a] == dist[b] && a < b);} };set<int,cmp> s;void add(int u,int v,int w) {edge[cnt].to = v;edge[cnt].next = head[u];edge[cnt].w = w;head[u] = cnt++; }void Init() {cnt = 0;s.clear();memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));for(int i=0;i<N;i++)dist[i] = INF; }void Dijkstra(int v) {dist[v] = 0;s.insert(v);while(!s.empty()){v = *s.begin();s.erase(v);vis[v] = 1;for(int i=head[v];~i;i=edge[i].next){int t = edge[i].to;if(!vis[t] && dist[t] > dist[v] + edge[i].w){s.erase(t);dist[t] = dist[v] + edge[i].w;s.insert(t);}}} }int main() {int n,m;while(~scanf("%d%d",&n,&m)){Init();for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);add(u,v,w);}int s,t;scanf("%d%d",&s,&t);Dijkstra(s);if(dist[t] == INF) puts("-1");else printf("%d\n",dist[t]);}return 0; }

題目：http://acm.hdu.edu.cn/showproblem.php?pid=3790

題意：給你n個點，m條無向邊，每條邊都有長度d和花費c，給你起點s和終點t，要求輸出起點到終點的最短距離及其花費，如果最短距離有

多條路線，則輸出花費最少的。

分析：本題是雙重權值的最短路徑問題，當然最法跟一般的最短路做法差不多。

#include <iostream> #include <string.h> #include <stdio.h>const int N = 1005; const int INF = 1<<29;bool vis[N]; int d[N],c[N]; int map[N][N]; int cost[N][N]; int m,n,s,t;void Init() {memset(vis,0,sizeof(vis));for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){map[i][j] = (i == j) ? 0 : INF;cost[i][j] = (i == j) ? 0 : INF;}} }void Dijkstra(int cur) {vis[cur] = 1;for(int i=1; i<=n; i++){d[i] = map[cur][i];c[i] = cost[cur][i];}for(int i=2; i<=n; i++){int k = cur;int minval = INF;for(int j=1; j<=n; j++){if(!vis[j] && d[j] < minval){minval = d[j];k = j;}}vis[k] = 1;for(int j=1; j<=n; j++){if(!vis[j]){if(d[j] > d[k] + map[k][j]){d[j] = d[k] + map[k][j];c[j] = c[k] + cost[k][j];}else if(d[j] == d[k] + map[k][j] && c[j] > c[k] + cost[k][j])c[j] = c[k] + cost[k][j];}}}if(d[t] == INF) puts("1");else printf("%d %d\n",d[t],c[t]); }int main() {while(~scanf("%d%d",&n,&m)){if(n==0 && m==0) break;Init();while(m--){int u,v,x,y;scanf("%d%d%d%d",&u,&v,&x,&y);if((map[u][v] > x) || (map[u][v] == x && cost[u][v] > y)){map[u][v] = map[v][u] = x;cost[u][v] = cost[v][u] = y;}}scanf("%d%d",&s,&t);Dijkstra(s);}return 0; }

總結

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

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