九度oj题目1341:艾薇儿的演唱会

题目1341:艾薇儿的演唱会(40分)

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:522

解决:237

题目描述:

艾薇儿今天来到了中国,她计划两天后在哈尔滨举行一场个人的演唱会。由于出现了紧急情况,演唱会的举办方要求艾薇儿提前举行演唱会。艾薇儿现在在北京,她需要找出一条从北京到哈尔滨耗时最短的线路,以便尽快到达哈尔滨。
 中国的铁路线非常复杂,有很多条路线可以从北京到达哈尔滨。艾薇儿在网上找到了铁路线各个线路上所需花费的时间,但是她还是看不出来哪一条线路可以最快地到达哈尔滨。你有办法帮助艾薇儿找出从北京到哈尔滨所需的最短时间吗?找出来的人可以免费获得现场演唱会门票一张哦。

输入:

 输入的第一行包括一个整数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个,但不保证所有的城市都能互相到达。可以保证的是,从北京到哈尔滨一定会有一条通路。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 #include <iostream>
 5 using namespace std;
 6 int map[105][105],dis[105];
 7 #define max 1000001
 8 int main(){
 9     //freopen("D:\INPUT.txt","r",stdin);
10     int n,m,a,b,d;
11     while(cin>>n>>m>>a>>b){
12         int i,j;
13         for(i=0;i<=n;i++){
14             dis[i]=max;
15             for(j=0;j<=n;j++){
16                 map[i][j]=max;//无穷大
17             }
18         }
19         dis[a]=0;
20         int aa,bb,t;
21         for(i=0;i<m;i++){
22             scanf("%d %d %d",&aa,&bb,&t);
23             if(map[aa][bb]>t)
24             map[aa][bb]=map[bb][aa]=t;
25         }
26         for(i=1;i<=n;i++){
27             if(i!=a)
28             dis[i]=map[a][i];
29         }
30         for(i=1;i<n;i++){//最短path,最多循环n-1次
31             int min=max;
32             int mink=-1;
33             for(j=1;j<=n;j++){
34                 if(dis[j]&&min>dis[j]){//dis[j]=0 表示j已访问过
35                     min=dis[j];
36                     mink=j;
37                 }
38             }
39             for(j=1;j<=n;j++){//update
40                 if(dis[j]>dis[mink]+map[mink][j]){
41                     dis[j]=dis[mink]+map[mink][j];
42                 }
43             }
44             if(mink==b){
45                 d=dis[mink];
46                 break;
47             }
48             dis[mink]=0;
49         }
50         cout<<d<<endl;
51     }
52     return 0;
53 }
原文地址:https://www.cnblogs.com/Deribs4/p/4633621.html