本文共 1171 字，大约阅读时间需要 3 分钟。

这里 需要注意 输入边的时候 可能重复输入 I - > j的边 需要判断 map[I][j] > w 选择 多次输入中最小的边

dijkstra

#include
   
    #include
    
     #define MAX 300#define INF 999999999using namespace std;int map[MAX][MAX];int dis[MAX];bool vis[MAX];int n, m;void dijkstra(int s){	int i, j, v;	memset(vis,false,sizeof(vis));	for(i = 0; i < n; ++i){		dis[i] = map[s][i];	}	dis[s] = 0; 	vis[s] = true;	while(true){		v = -1;		for(int u = 0; u < n; ++u){			if(!vis[u] && ( v == -1 || dis[u] < dis[v])){				v = u;							}		}		if(v == -1) break;		vis[v] = true;		for(int w = 0; w < n; ++w){			if(!vis[w] && map[v][w] < INF && map[v][w] != 0){				if(dis[w] > dis[v] + map[v][w])					dis[w] = dis[v] + map[v][w];			} 		}	}		}int main()	{		int i, j;		int s, e;		while(scanf("%d%d",&n,&m) != EOF){			for(i = 0; i < n; ++i){				for(j = 0; j < n; ++j){					if(i == j){						map[i][j] = 0;					}					else						map[i][j] = INF;				}			}						int a, b, w;			for(i = 0; i < m; ++i){				scanf("%d%d%d",&a,&b,&w);				if(map[a][b] > w) //这里要注意 可能多次输入边 I, j 选取小的 					map[a][b] = map[b][a] = w;			}			scanf("%d%d",&s,&e);			dijkstra(s);			if(dis[e] == INF){				printf("%d\n",-1);			}			else				printf("%d\n",dis[e]);		}			return 0;	}
    
   

转载地址：http://xmimi.baihongyu.com/