首页 > 代码库 > HDOJ 1874 畅通工程续 【dijkstra】
HDOJ 1874 畅通工程续 【dijkstra】
题意:。。。
策略:最简单的求最短路径.
代码:
#include<stdio.h> #include<string.h> #define MAXN 1005 #define INF 0x3f3f3f3f int di[MAXN], vis[MAXN], n, m; int map[MAXN][MAXN]; void dijkstra(int v) { int i, j; memset(vis, 0, sizeof(vis)); di[v] = 0; vis[v] = 1; for(i = 0; i < n; i ++){ if(!vis[i]){ di[i] = map[v][i]; } } for(i = 1; i < n; i ++){ int min = INF; int min_pos = 0; for(j =0; j < n; j ++ ){ if(!vis[j]&&min > di[j]){ min_pos = j; min = di[j]; } } vis[min_pos] = 1; for(j = 0; j < n; j ++){ if(!vis[j]&&di[j] > di[min_pos]+map[min_pos][j]){ di[j] = di[min_pos]+map[min_pos][j]; } } } } int main() { int i, j, a, b, c, st, en; while(scanf("%d%d", &n, &m) == 2){ memset(map, 0, sizeof(map)); for(i = 0; i < n; i ++){ for(j = 0; j < n; j ++){ map[i][j] = i == j?0:INF; } } for(i = 0; i < m; i ++){ scanf("%d%d%d", &a, &b, &c); if(map[a][b]>c||!map[a][b]){ map[a][b] = map[b][a] = c; } } scanf("%d%d", &st, &en); dijkstra(en); if(di[st] != INF) printf("%d\n", di[st]); else printf("-1\n"); } return 0; }
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1874
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。