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