HDU 2066. 한 사람의 여행 [최 단 경로 (여러 번 Dijsktra 알고리즘)] [4 월 17]

혼자 만 의 여행
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 29171    Accepted Submission(s): 10021
Problem Description
비록 풀 은 길 치 이지 만 (항 저 우 전기 에서 1 년 넘 게 있 었 는데 도 캠퍼스 에서 길 을 잃 은 사람, 땀 ~) 풀 은 여전히 여행 을 좋아 합 니 다. 여행 중 에 많은 사람들 을 만 날 수 있 기 때 문 입 니 다 (백마 탄 왕자, ^ 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
   
   
   
   

 
매번 인접 한 점 을 기점 으로 dijsktra 를 만 들 고 작은 값 을 취한 다.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 1010;
#define INF 0x3f3f3f3f
int T, S, D, a, b ,time, city;
int dist[MAXN], vt[MAXN], len[MAXN][MAXN];
void Dijkstra(int root)//  
{
    memset(vt, 0, sizeof(vt));
    dist[root] = 0;
    vt[root] = 1;
    for(int i = 1; i <= T; ++i)
    {
        int minx = INF;
        for(int j = 1; j < MAXN; ++j)
        {
            if(vt[j] == 1) continue;
            if(len[root][j] == INF) continue;
            if(dist[j] > dist[root] + len[root][j])
            {
                dist[j] = dist[root] + len[root][j];
            }
        }
        for(int j = 1; j < MAXN; ++j)
        {
            if(vt[j] == 0 && dist[j] < minx)
            {
                root = j;
                minx = dist[j];
            }
        }
        vt[root] = 1;
    }
}
int main()
{
    while(scanf("%d %d %d", &T, &S, &D) != EOF)
    {
        memset(len, 0x3f, sizeof(len));
        memset(dist, 0x3f, sizeof(dist));
        for(int i = 1; i <= T; ++i)
        {
            scanf("%d %d %d", &a, &b, &time);
            len[a][b] = len[b][a] = min(len[a][b], time);
        }
        while(S--)//           
        {
            scanf("%d", &city);
            Dijkstra(city);
        }
        int ans = INF;
        while(D--)
        {
            scanf("%d", &city);
            ans = min(ans, dist[city]);
        }
        cout << ans << endl;
    }
    return 0;
}