Problem Description雖然草兒是個路癡（就是在杭電待了一年多，居然還會在校園里迷路的人，汗~),但是草兒仍然很喜歡旅行，因為在旅途中 會遇見很多人（白馬王子，^0^），很多事，還能豐富自己的閱歷，還可以看美麗的風景……草兒想去很多地方，她想要去東京鐵塔看夜景，去威尼斯看電影，去陽明山上看海芋，去紐約純粹看雪景，去巴黎喝咖啡寫信，去北京探望孟姜女……眼看寒假就快到了，這么一大段時間，可不能浪費啊，一定要給自己好好的放個假，可是也不能荒廢了訓練啊，所以草兒決定在要在最短的時間去一個自己想去的地方！因為草兒的家在一個小鎮上，沒有火車經過，所以她只能去鄰近的城市坐火車（好可憐啊~）。
Input輸入數據有多組，每組的第一行是三個整數T，S和D，表示有T條路，和草兒家相鄰的城市的有S個，草兒想去的地方有D個；
接著有T行，每行有三個整數a，b，time,表示a,b城市之間的車程是time小時；(1=<(a,b)<=1000;a,b 之間可能有多條路)
接著的第T+1行有S個數，表示和草兒家相連的城市；
接著的第T+2行有D個數，表示草兒想去地方。
Output輸出草兒能去某個喜歡的城市的最短時間。
Sample Input6 2 3 1 3 5 1 4 7 2 8 12 3 8 4 4 9 12 9 10 2 1 2 8 9 10
Sample Output9開始用了Floyd的算法，無奈超時，因為一開始沒有往單元最短路上想，以為是數組初始化上超時，后來看了別人的博客，才發現此題可以用Dijkstra來解，把草兒的家看做一個點，到其最近的車站的費用為0（真是巧妙的想法）。這樣，這個題就完完全全變成了單元最短路的問題！code：

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include <algorithm>
using namespace std;

const int INF=0x3f3f3f3f;
const int N=1005;
int n;
int mp[N][N];
int dp[N],vis[N];

void Dijkstra() //單源最短路
{
int i,j;
int x,t;
memset(vis,0,sizeof(vis));
for (i=0;i<n;i++) dp[i]=mp[0][i];
vis[0]=1;
for (i=0;i<n;i++)
{
t=INF;
for (j=0;j<n;j++)
if (!vis[j]&&dp[j]<t) x=j,t=dp[x];
if (t>=INF) break;
vis[x]=1;
for (j=0;j<n;j++)
if (!vis[j])
dp[j]=min(dp[j],dp[x]+mp[j][x]);
}
}

int main(){

int T,S,D;
while (cin>>T>>S>>D)
{
int i,j;
int u,v,w;
int s,t;
n=-1;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
mp[i][j]=(i==j?0:INF);
memset(mp,INF,sizeof(mp));
for(i=0;i<T;i++)
{
scanf("%d%d%d",&u,&v,&w);
n=max(n,max(u,v));
if(mp[u][v]>w)
mp[u][v]=mp[v][u]=w;
}
n++;
for (i=0;i<S;i++)
{
scanf("%d",&s);
mp[0][s]=mp[s][0]=0;
}
Dijkstra();
int ans=INF;
for (i=0;i<D;i++) //找出最小的費用即可
{
scanf("%d",&t);
ans=min(dp[t],ans);
}
printf("%d\n",ans);
}
return 0;
}

總結

以上是生活随笔為你收集整理的HDU2066：一个人的旅行的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。