题目:http://acm./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./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;}
