hdu2066 一個人的旅行

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 Input

6 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 Output

9      

該題也是一個 最短路徑的題目。首先題目的意思就是找出 幾個城市是在一個源點      

上的，然後，在想要去的城市中，找到一個最少話費時間的城市。      

隻要先把幾個在一個源點的城市周遊一遍，找出與他話費時間最少的 想要去的城市即可；      

我最初在main中直接2個for循環周遊源點和重點，結果 tle了，，然後，，把終點城市      

的判斷放在了上面，，才ac      

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cmath>
using namespace std;
const int INF=1e9+1;
int T,S,D;
int minn;
int a,b,time;
int d[1010][1010];
int s1[1010];//和草兒相鄰的城市 
int s2[1010];//草兒想要去的城市 
int maxn,m;
int num[1010];
int biao[1010];
int sou(int shi)
{
	int k;
	memset(biao,0,sizeof(biao));
	for(int i=1;i<=maxn;i++)
	{
		num[i]=d[shi][i];//shi表示 從草兒城市開始的到各個城市的距離 
	}
	num[shi]=0;
	for(int i=1;i<=maxn;i++)
	{
		m=INF;
		for(int j=1;j<=maxn;j++)
		{
			if(biao[j]==0&&num[j]<m)
			{
				k=j;
				m=num[j];
			}
		}
		if(m==INF) break;
		biao[k]=1;
		
		for(int j=1;j<=maxn;j++)
		{
			if(biao[j]==0&&num[j]>num[k]+d[k][j])
			num[j]=num[k]+d[k][j];
		}
	}
	int d_min=INF;
	for(int i=0;i<D;i++) //判斷目标城市的最小花費時間 
	{
		if(num[s2[i]]<d_min)
		d_min=num[s2[i]];
	}
	return d_min;
}




int main()
{
	
	while(cin>>T>>S>>D)
	{
		maxn=-1;
		minn=INF;
		memset(d,INF,sizeof(d));
		for(int i=1;i<=T;i++)
		{
			cin>>a>>b>>time;
			if(a>maxn) maxn=a;
			if(b>maxn)  maxn=b;
			if(d[a][b]>time)
			{
				d[a][b]=time;
				d[b][a]=time;
			}
		}
		for(int i=0;i<S;i++)
		{
			cin>>s1[i];
		}
		for(int i=0;i<D;i++)
		cin>>s2[i];
		
		int tot=0;
		for(int i=0;i<S;i++)
		{
			tot=sou(s1[i]);//不同的源點，尋找最小花費時間的城市 
			if(tot<minn)  minn=tot;
		}
		cout<<minn<<endl;
	}
    return 0;
}