九度-1341-艾薇儿的演唱会[最短路径] | Acm之家
Read full article from 九度-1341-艾薇儿的演唱会[最短路径] | Acm之家
- 艾薇儿今天来到了中国,她计划两天后在哈尔滨举行一场个人的演唱会。由于出现了紧急情况,演唱会的举办方要求艾薇儿提前举行演唱会。艾薇儿现在在北京,她需要找出一条从北京到哈尔滨耗时最短的线路,以便尽快到达哈尔滨。
中国的铁路线非常复杂,有很多条路线可以从北京到达哈尔滨。艾薇儿在网上找到了铁路线各个线路上所需花费的时间,但是她还是看不出来哪一条线路可以最快地到达哈尔滨。你有办法帮助艾薇儿找出从北京到哈尔滨所需的最短时间吗?找出来的人可以免费获得现场演唱会门票一张哦。
- 输入:
- 输入的第一行包括一个整数N(2<=N<=100),代表艾薇儿手上拿到的设有铁路站点的城市的个数,其中城市从1到n进行编号。以及M(1<=M<=1000),代表有M条铁路线路,每条铁路线路只连接两个城市。
接下来的一行有两个数,a和b(1<=a,b<=N),分别表示北京和哈尔滨的编号。
接下来有M行,每行有三个数x,y(1<=x,y<=N),t(1<=t<=1000),表示从城市x到城市y所需时间为t。
- 输出:
- 请输出艾薇儿从北京到哈尔滨最少需要多长时间。你可以放心地认为肯定存在一条路线可以从北京到哈尔滨。
- 样例输入:
3 4 1 3 1 2 1 3 2 3 2 3 4
3 1 8
- 样例输出:
4
- 提示:
- 1.火车能从城市x到城市y,就能从城市y到城市x,并且同一列火车来回所花费的时间是一样的。如果在x和y之间有不止一辆火车通行,则不同火车从x到y或者从y到x所花费的时间可能不相同。
2.虽然城市数有N个,但不保证所有的城市都能互相到达。可以保证的是,从北京到哈尔滨一定会有一条通路
08 | void Dijkstra() |
09 | { |
10 | int i, j, k, min; |
11 | for (i = 1; i <= n; ++i) |
12 | spand[i] = map[s][i]; |
13 | visit[s] = 1; |
14 | spand[s] = 0; |
15 | for (i = 2; i <= n; ++i) |
16 | { |
17 | k = -1, min = INF; |
18 | for (j = 1; j <= n; ++j) |
19 | { |
20 | if (!visit[j] && spand[j] < min) |
21 | { |
22 | k = j; |
23 | min = spand[j]; |
24 | } |
25 | } |
26 | if (k == -1) |
27 | break ; |
28 | visit[k] = 1; |
29 | for (j = 1; j <= n; ++j) |
30 | { |
31 | if (!visit[j] && spand[k] + map[k][j] < spand[j]) |
32 | spand[j] = spand[k] + map[k][j]; |
33 | } |
34 | } |
35 | printf ( "%d\n" ,spand[e]); |
36 | } |
37 |
38 | int main() |
39 | { |
40 | while ( scanf ( "%d%d%d%d" , &n,&m,&s,&e) != EOF) |
41 | { |
42 | int i, j; |
43 | memset (map, 0x3f, sizeof (map)); |
44 | memset (spand, 0x3f, sizeof (spand)); |
45 | memset (visit,0, sizeof (visit)); |
46 | int x, y, t; |
47 | while (m--) |
48 | { |
49 | scanf ( "%d%d%d" , &x,&y,&t); |
50 | if (map[x][y] > t) |
51 | map[x][y] = map[y][x] = t; |
52 | } |
53 | Dijkstra(); |
54 | } |
55 | return 0; |
56 | } |