poj 2066一人旅最短

一人の旅行、テーマリンク、click here.
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 29537 Accepted Submission(s): 10147
Problem Description
草児は方向音痴(杭電に1年以上いたのに、キャンパスで道に迷った人、汗~)でしたが、草児は旅行が大好きで、旅の途中でたくさんの人に会えるので(白馬王子、^0^)ああ、いろいろなことがあって、自分の経験を豊かにすることができて、また美しい景色を见ることができます......草は多くの地方に行きたいです.彼女は东京タワーに行って夜景を见に行きたいです.ベネチアに行って映画を见に行きます.阳明山に行って芋を见に行きます.ニューヨークに行って雪の景色を见に行きます.パリに行ってコーヒーを饮んで手纸を书きます.北京に行って孟姜女を见舞いに行きます.冬休みが近づいています.ちゃんと休みを取ってあげなきゃいけないんだけど、訓練をおろそかにしちゃいけないんだから、草は一番短い時間で行きたいところに行くことにしたんだよ.草の家は小さな町にあって列車が通っていないから、隣の町に行って列車に乗るしかないんだよ(かわいそう~).
Input
入力データは複数組あり、各組の1行目は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
題意:t本の道、s個の隣接都市、t個の目標都市を与え、s個の隣接都市のうちの1都市からt個の目標都市のうちの1都市までの最小の距離を求める.
フロイドアルゴリズムの構想:テンプレートをセットして、s個の都市とt個の目標都市をそれぞれ配列に保存して、s個の都市の中の1つとt個の目標都市の中の1つが現れた時、判断して、最短距離をメモします.

#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<vector>
#include<stdio.h>
using namespace std;
#define maxn 10005
#define inf 0x3f3f3f
int dis[maxn];//   ；
int map[1005][1005];//  ；
int endd[maxn],star[maxn];//   s   ，t   ；
int main()
{
    int a,b,c,s,o,temp,S,T,D;
    while(~scanf("%d%d%d",&T,&S,&D))
    {
        memset(endd,0,sizeof(endd));//  endd  ;
        memset(star,0,sizeof(star));//  star  ;
        //       ，    ，    。
        //memset(map,0x3f3f,sizeof(map));
        //for(int i=1;i<=1000;i++)
        // map[i][i]=0;
        int size_map=0;
        for(int j=0; j<=1000; j++)
            for(int i=0; i<=1000; i++)
            {
                if(i==j)
                    map[i][i]=0;
                else
                    map[i][j]=inf;
            }

        //  ,T  ;
        for(int i=1; i<=T; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            size_map=max(size_map,max(a,b));
            if(map[a][b]>c)
                map[a][b]=map[b][a]=c;
        }
        // s   ;
        for(int i=1; i<=S; i++)
        {
            scanf("%d",&temp);
            star[temp]=1;
        }
        // D   ;
        for(int i=1; i<=D; i++)
        {
            scanf("%d",&temp);
            endd[temp]=1;
        }
        int ninn=inf;
        //      ;
        for(int k=1; k<=size_map; k++)
            for(int i=1; i<=size_map; i++)
                if(map[i][k]!=inf)//  ，  ，    ;
                    for(int j=1; j<=size_map; j++)
                    {
                        if(map[i][j]>map[i][k]+map[k][j])
                            map[i][j]=map[i][k]+map[k][j];
                        //        s     、t     ，      ninn，  ;
                        if(star[i]==1&&endd[j]==1&&map[i][j]<ninn)
                            ninn=map[i][j];
                    }
        printf("%d
",ninn);
    }
    return 0;
}

ディジェストラ:簡略化すると、草を近くの都市から目標都市まで直接見る--彼女の家から目標都市までの距離は、最初は彼女の家から近くの都市までの距離をゼロにし、すべての目標都市から(0,0)までの最小距離を求めます.

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string>
#include<string.h>
#include<math.h>
using namespace std;
#define inf 0x3f3f3f
#define maxn 1005
int dis[maxn],map[maxn][maxn],vis[maxn],star[maxn],endn[maxn];
int main()
{
    int m,n,size_map,a,b,c,t;
    while(~scanf("%d%d%d",&n,&m,&t))// n  ，s     ，d     ；
    {
        memset(vis,0,sizeof(vis));
        memset(map,0x3f3f,sizeof(map));
        for(int i=0;i<=1005;i++)
            map[i][i]=0;
        //  ；
        //          ；
        size_map=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            size_map=max(size_map,max(a,b));
            if(map[a][b]>c)
                map[a][b]=map[b][a]=c;
        }

        //    ；
        for(int i=0;i<m;i++)
        {
            scanf("%d",&star[i]);
            map[star[i]][0]=map[0][star[i]]=0;
            //          ；
        }

        // t      ;
        for(int i=0;i<t;i++)
            scanf("%d",&endn[i]);
        //       ;
        for(int i=0;i<=size_map;i++)
            dis[i]=map[0][i];

        //          ;
        vis[0]=1;
        int minn,u;
        for(int i=1;i<=size_map;i++)
        {
            minn=inf;
            for(int j=1;j<=size_map;j++)
            {
                if(vis[j]==0&&dis[j]<minn)
                {
                    minn=dis[j];
                    u=j;
                }
            }
            vis[u]=1;
            for(int v=1;v<=size_map;v++)
                if(map[u][v]<inf&&dis[v]>dis[u]+map[u][v])
                    dis[v]=dis[u]+map[u][v];
        }
        minn=inf;//          ;
        //               ;
        for(int i=0;i<t;i++)
                minn=min(minn,dis[endn[i]]);
        printf("%d
",minn);
    }
    return 0;
}

最初は回り道かと思っていたのですが、隣の町から目的の町までの最短距離を見つけて、後になって問題を見間違えていたことを知りましたが、気づいたときはもう長い間やっていました.最初は見当がつかなかったのですが、意外にも簡単でしたが、いろいろ考えが湧いてきて、大神の指導の下、Aに行きました.wu~楊楊楊に感謝します「先輩」!!!