HDU 2066一人旅(最短経路)

一人旅
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 18343    Accepted Submission(s): 6372
Problem Description
草は方向音痴(杭電に1年以上いたのに、校庭で道に迷った人、汗~)だが、草は旅行が大好きで、旅の途中でたくさんの人に出会うから(白馬王子、^0^)ああ、いろいろなことがあって、自分の経験を豊かにすることができて、きれいな景色を见ることができます......草はとても多くの地方に行きたいです.彼女は东京タワーに行って夜景を见に行きたいです.ベネチアに行って映画を见に行きます.阳明山に行って芋を见に行きます.ニューヨークに行って雪の景色を见に行きます.パリに行ってコーヒーを饮んで手纸を书きます.ああ、ちゃんと休みを取ってあげなきゃいけないんだけど、訓練をおろそかにしちゃいけないんだから、草は一番短い時間で行きたいところに行くことにしたんだよ.草の家は小さな町にあって列車が通っていないから、隣の町に行くだけで汽車に乗れたんだよ(かわいそうだね~).
 
Input
入力データには複数のグループがあり、各グループの最初の行は3つの整数T、S、Dであり、T本の道があり、草の家と隣接する都市にはS個、草の行きたい場所にはD個があることを示している.
次にT行があり、各行に3つの整数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
   
     

 
Author
Grass
 
Source
RPG特別練習試合
 
Recommend
lcy   |   We have carefully selected several similar problems for you:  
1874  
2112  
1217  
1142  
1385
コード:78 MS

#include<stdio.h>
#include<string.h>
#define INF 1000000
#define maxn 1100
int want[maxn]; int map[maxn][maxn]; int near[maxn]; int mark[maxn]; int dis[maxn]; int mc; void dijkstra(int x) { int i,j,k,minx;
    memset(mark,0,sizeof(mark));//       ，           。 
 for(i=0;i<=mc;i++)
        dis[i]=map[x][i];// x  i     dis[i]。 
    mark[x]=1;//  x     
    dis[x]=0;//       x           。   
 for(i=1;i<=mc;i++) {
        minx=INF; for(j=0;j<=mc;j++) { if(mark[j]==0 && dis[j]<minx)//         ，       。
 {
                minx=dis[j];
                k=j; } }
        mark[k]=1; for(j=0;j<=mc;j++) { if(mark[j]==0 && dis[j]>dis[k]+map[k][j]) //              。 
 {
                dis[j]=dis[k]+map[k][j]; } } } } int main() { int min,i,j,a,b,c,t,s,d; while(scanf("%d%d%d",&t,&s,&d)!=EOF) {
        min=INF;
        mc=0; for(i=0;i<maxn;i++) { for(j=0;j<maxn;j++) { if(i==j) 
                map[i][j]=0; else map[i][j]=map[j][i]=INF;//         。 
 } } for(i=1;i<=t;i++) {
            scanf("%d%d%d",&a,&b,&c); if(map[a][b]>c) {
                map[a][b]=c;
                map[b][a]=c; }
            mc=(a>b?a:b)>mc?(a>b?a:b):mc;//         ，   。 
 } for(i=1;i<=s;i++) {
            scanf("%d",&near[i]); } for(i=1;i<=s;i++) {
            map[0][near[i]]=map[near[i]][0]=0; } for(i=1;i<=d;i++) {
            scanf("%d",&want[i]); }
        dijkstra(0); for(i=1;i<=d;i++) { if(dis[want[i]]<min) {
                min=dis[want[i]]; } }
        printf("%d
",min); } return 0; }