54
九度题目1341：艾薇儿的演唱会
题目1341：艾薇儿的演唱会(40分)
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：412
解决：192
题目描述：
艾薇儿今天来到了中国，她计划两天后在哈尔滨举行一场个人的演唱会。由于出现了紧急情况，演唱会的举办方要求艾薇儿提前举行演唱会。艾薇儿现在在北京，她需要找出一条从北京到哈尔滨耗时最短的线路，以便尽快到达哈尔滨。
中国的铁路线非常复杂，有很多条路线可以从北京到达哈尔滨。艾薇儿在网上找到了铁路线各个线路上所需花费的时间，但是她还是看不出来哪一条线路可以最快地到达哈尔滨。你有办法帮助艾薇儿找出从北京到哈尔滨所需的最短时间吗？找出来的人可以免费获得现场演唱会门票一张哦。
输入：
输入的第一行包括一个整数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个，但不保证所有的城市都能互相到达。可以保证的是，从北京到哈尔滨一定会有一条通路。
思路：典型的佛洛依德算法，只不过有一点稍微不同的是，从x至y不止一种火车，也就是从x至y和y只x有多种行车时间，这里我们
要做的仅仅是取最小的那一个时间的火车就行了
AC代码：（数据只有一组）
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define INF 0x11111111
int a[110][110],b[110][110];
void Fun()
{
int i,j,p;
for(i=0;i<110;i++)
{
for(j=0;j<110;j++)
b[i][j]=a[i][j];
b[i][i]=0;
}
for(i=0;i<110;i++)
for(j=0;j<110;j++)
for(p=0;p<110;p++)
{
if(b[j][i]+b[i][p]<b[j][p])
{
b[j][p]=b[j][i]+b[i][p];
}
}
}
int main()
{
int i,j,n,m,st,en,x,y,len;
scanf("%d %d",&n,&m);
scanf("%d %d",&st,&en);
memset(a,INF,sizeof(a));
memset(b,INF,sizeof(b));
for(i=0;i<m;i++)
{
scanf("%d %d %d",&x,&y,&len);
if(a[x][y]==INF)
{
a[x][y]=len;
a[y][x]=len;
}
else
{
if(len<a[x][y])
{
a[x][y]=len;
a[y][x]=len;
}
}
}
Fun();
printf("%d\n",b[st][en]);
return 0;
}
最后更新：2017-04-03 12:56:23