一个人的旅行(最短路).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
using namespace std;
#define Max 1100
#define INF 0x7fffff

int road[Max][Max];
int t,s,d,maxd;
int pv[Max];

int Dijkstra(int n)
{
    bool final[Max];// solved vertex
    int i,j,min,vmin;
    
    memset(final,0,sizeof(final));
    
    final[0]=true;
    for(i=1;i<=n;i++)
    {
        min=INF;
        vmin=0;
        for(j=1;j<=n;j++) // select min value vertex
            if(!final[j] && pv[j]<min)
            {    min=pv[j];vmin=j;}
        final[vmin]=true;
            
            for(j=1;j<=n;j++) // refresh pv
                if(!final[j] && road[vmin][j]!=0 && pv[j]> min+road[vmin][j])
                {
                    pv[j]=min+road[vmin][j];
                }
    }
    
    return pv[n]-1;
}

int main()
{
    int i,a,b,time,mins,ts;
    
    while(scanf("%d%d%d",&t,&s,&d)!=EOF)
    {
        memset(road,0,sizeof(road));
        memset(pv,9999,sizeof(pv));
        maxd=-1;
        for(i=0;i<t;i++)
        {
            scanf("%d%d%d",&a,&b,&time);
            if(road[a][b]==0 || time < road[a][b])
                road[a][b]=road[b][a]=time;
            maxd= maxd>a ? maxd : a;
            maxd= maxd>b ? maxd : b;
        }
        for(i=0;i<s;i++)
        {
            scanf("%d",&ts);
            road[0][ts]=0;
            pv[ts]=0;
        }
        for(i=0;i<d;i++)
        {
            scanf("%d",&ts);
            road[ts][maxd+1]=1;
        }
        
        mins=INF;
        mins=Dijkstra(maxd+1);
        printf("%d\n",mins);
    }
}