hdoj 1874 单源最短路径

本文主要是介绍hdoj 1874 单源最短路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

dijkstra

#include<iostream>
#include<string.h>
#define MAX 300
#define INF 999999999
using 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;}elsemap[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);}elseprintf("%d\n",dis[e]);}return 0;} 

这篇关于hdoj 1874 单源最短路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---