一个人的旅行

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 18399    Accepted Submission(s): 6394

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

9

#include<iostream>

#include<cstring>

using namespace std;

#define M 1005

#define N 100000

int map[M][M],v[M],d[M];

int a[M],b[M];

void Dijkstra(int n)

{

	int i,j,min,p;

	for(i=0;i<=n;i++)

	{

		d[i]=map[0][i];

		v[i]=0;

	}

	v[0]=1;

	for(i=0;i<=n;i++)

	{

		min=N;

		for(j=1;j<=n;j++)

			if(v[j]==0 && d[j]<min)

			{

				min=d[j];

				p=j;

			}

		v[p]=1;

		for(j=1;j<=n;j++)

			if(v[j]==0 && d[j]>d[p]+map[p][j])

				d[j]=d[p]+map[p][j];

	}

}

int main()

{

	int T,S,D;

	while(cin>>T>>S>>D)

	{

		int i,j;

		for(i=0;i<M;i++)

			for(j=0;j<M;j++)

			{

				if(i==j)

					map[i][j]=0;

				else

					map[i][j]=N;

			}

		int x,y,time,max=0;

		for(i=0;i<T;i++)

		{

			cin>>x>>y>>time;

			if(map[x][y]>time)

				map[x][y]=map[y][x]=time;

			if(x>max)  max=x;

			if(y>max)  max=y;

		}

		for(i=1;i<=S;i++)

		{

			cin>>a[i];

			map[a[i]][0]=map[0][a[i]]=0;

		}

		for(i=1;i<=D;i++)

			cin>>b[i];

		Dijkstra(max);

		int min=N;

		for(j=1;j<=D;j++)

			if(min>d[b[j]])

				min=d[b[j]];

		cout<<min<<endl;

	}

	return 0;

}