摘要:
最短路径 Dijkstra算法
问题描述 G国国王来中国参观后,被中国的高速铁路深深的震撼,决定为自己的国家也建设一个高速铁路系统。 建设高速铁路投入非常大,为了节约建设成本,G国国王决定不新建铁路,而是将已有的铁路改造成高速铁路。现在,请你为G国国王提供一个方案,将现有的一部分铁路改造成高速铁路,使得任何两个城市间都可以通过高速铁路到达,而且从所有城市乘坐高速铁路到首都的最短路程和原来一样长。请你告诉G国国王在这些条件下最少要改造多长的铁路。
输入格式 输入的第一行包含两个整数n , m ,分别表示G国城市的数量和城市间铁路的数量。所有的城市由1到n 编号,首都为1号。 接下来m 行,每行三个整数a , b , c ,表示城市a 和城市b 之间有一条长度为c 的双向铁路。这条铁路不会经过a 和b 以外的城市。
输出格式 输出一行,表示在满足条件的情况下最少要改造的铁路长度。
样例输入 4 5 1 2 4 1 3 5 2 3 2 2 4 3 3 4 2
样例输出 11
评测用例规模与约定 对于20%的评测用例,1 ≤ n ≤ 10,1 ≤ m ≤ 50; 对于50%的评测用例,1 ≤ n ≤ 100,1 ≤ m ≤ 5000; 对于80%的评测用例,1 ≤ n ≤ 1000,1 ≤ m ≤ 50000; 对于100%的评测用例,1 ≤ n ≤ 10000,1 ≤ m ≤ 100000,1 ≤ a , b ≤ n,1 ≤ c ≤ 1000。输入保证每个城市都可以通过铁路达到首都。
AC代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 #include <iostream> #include <algorithm> #include <vector> using namespace std ;const int INF = 0x3f3f3f3f ;const int MAXN = 10010 ;struct Edge { int v, w; }edge; int vis[MAXN];int dis[MAXN];int pre[MAXN]; vector <Edge>map [MAXN];int n, m;void dijkstra (int s) { fill(dis, dis + MAXN + 1 , INF); fill(pre, pre + MAXN + 1 , 0 ); fill(vis, vis + MAXN + 1 , 0 ); int u, MIN; dis[s] = 0 ; for (int i = 1 ; i <= n; i++) { u = -1 , MIN = INF; for (int j = 1 ; j <= n; j++) { if (vis[j] == 0 && dis[j] < MIN) { MIN = dis[j]; u = j; } } if (u == -1 )return ; vis[u] = 1 ; for (int j = 0 ; j < map [u].size(); j++) { int temp = map [u][j].v; if (vis[temp] == 0 && dis[u] + map [u][j].w <= dis[temp]) { if (dis[u] + map [u][j].w == dis[temp] && map [u][j].w < pre[temp]) pre[temp] = map [u][j].w; else { dis[temp] = dis[u] + map [u][j].w; pre[temp] = map [u][j].w; } } } } } int main () { int a, b, c, ans; struct Edge my_edge ; cin >> n >> m; ans = 0 ; for (int i = 0 ; i < m; i++) { cin >> a >> b >> c; my_edge.v = b; my_edge.w = c; map [a].push_back(my_edge); my_edge.v = a; map [b].push_back(my_edge); } dijkstra(1 ); for (int i = 1 ; i <= n; i++) ans += pre[i]; cout << ans << endl ; return 0 ; }