가장 짧 은 경로 중 하나 인 개인의 여행

혼자 만 의 여행
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 19403    Accepted Submission(s): 6787
Problem Description
풀 은 길 치 였 지만 풀 은 여전히 여행 을 좋아 했다.
여행 중 많은 사람들 을 만 날 수 있 기 때 문 입 니 다(백마 탄 왕자,^0^).많은 일 들 이 자신의 경험 을 풍부하게 하고 아름 다운 풍경 도 볼 수 있 기 때 문 입 니 다.
풀 은 많은 곳 을 가 고 싶 어한 다.그녀 는 도 쿄 철탑 에 가서 야경 을 보고 베니스 에 가서 영 화 를 보고 양 명산 에 가서 토란 을 보고 뉴욕 에 가서 순 전 히 설경 을 보고 싶다.
파리 에 가서 커피 를 마시고 편 지 를 쓰 고 베 이 징 에 가서 맹 강 녀 를 방문 하 다.
반드시 자신 에 게 휴가 를 잘 보 내야 한다.그러나 훈련 을 소홀히 해 서 는 안 된다.그래서 풀 은 가장 짧 은 시간 에 자신 이 가 고 싶 은 곳 으로 가기 로 결정 했다!
풀 의 집 은 작은 마을 에 있어 기차 가 지나 가지 않 아 인근 도시 로 가서 기 차 를 탈 수 밖 에 없 었 다.
 
Input
입력 데 이 터 는 여러 그룹 이 있 습 니 다.각 그룹의 첫 줄 은 세 개의 정수 T,S 와 D 입 니 다.T 개의 길이 있 고 초아 집 과 인접 한 도 시 는 S 개 입 니 다.
풀이 가 고 싶 은 곳 은 D 개;
이 어 T 줄 이 있 고 줄 마다 세 개의 정수 a,b,time 이 있 으 며 a,b 도시 간 의 차 거 리 는 time 시간 임 을 나타 낸다.
(1=<(a,b)<=1000;이 가능 하 다,~할 수 있다,...
이 어 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
   
   
   
   

0 부터 출발한다 고 가정 하면,
풀 과 인접 한 도시 에 도착 하 는 시간 은 0 이다.
한 점 에서 다른 점 으로 바 뀌 는 문제.

#include <stdio.h>

const int INF=0xfffffff;

int dist[1005];		//       
int a[1005][1005];	//    
int n;		

void init()
{
	for(int i=0;i<=1000;i++)
		for(int j=0;j<=1000;j++)
			a[i][j]=(i==j?0:INF);
}

void dijkstra(int u)
{
	int sign[1005]={0};
	int x=u;
	int i,j;
	for(i=0;i<=n;i++)		//      
		dist[i]=a[x][i];
	dist[x]=0;
	sign[x]=1;

	for(i=0;i<=n-2;i++)		//   
	{
	    int min=INF;
	    for(j=0;j<=n;j++)
    	    {
		if(!sign[j] && min>dist[j])
		{
			min=dist[j];
			x=j;
		}
	    }
	    sign[x]=1;

	    for(j=0;j<=n;j++)		//      
	    {
		if(!sign[j] && a[x][j]<INF && dist[x]+a[x][j]<dist[j])
		    dist[j]=dist[x]+a[x][j];
	    }
	}
}

int fmin(int a,int b)
{
	return a>b?b:a;
}
int fmax(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	int t,s,d;
	int i;
	while(scanf("%d %d %d",&t,&s,&d)!=EOF)
	{
		init();
		n=0;
		for(i=1;i<=t;i++)
		{
			int x,y,z;
			scanf("%d %d %d",&x,&y,&z);
			a[x][y]=fmin(a[x][y],z);//    

			a[y][x]=fmin(a[y][x],z);//    
			n=fmax(n,x); //n     ，
			n=fmax(n,y);    //         。
		}
		for(i=1;i<=s;i++)
		{
			int x;
			scanf("%d",&x);
			a[0][x]=0;       //        0
			a[x][0]=0;
		}

		dijkstra(0);

		int min=INF,k;
		for(i=1;i<=d;i++)
		{
			scanf("%d",&k);
			min=fmin(min,dist[k]);
		}
		printf("%d
",min);

	}
	return 0;
}

개조 테스트 데이터 에 대해 dist 값 변 화 는 다음 과 같 습 니 다.
dist【0~n】