Description
Input
接着有T行,每行有三个整数a,b,time,表示a,b城市之间的车程是time小时;(1=<(a,b)<=1000;a,b 之间可能有多条路)
接着的第T+1行有S个数,表示和草儿家相连的城市;
接着的第T+2行有D个数,表示草儿想去地方。
Output
Sample Input
Sample Output
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXINT=1<<25;
int num0[1050][1050];
int num1[1050];
int dis[1050];//distance
bool flag0[1050];
int T,S,D,flag,MIN,m;
void dijkstra()
{
memset(flag0,0,sizeof(flag0));//重置标记数组
for(int i=0 ; i<=m ; i++)
dis[i]=num0[0][i];//各点到草儿家所需最小时间
flag0[0]=1;
dis[0]=0;
for(int i=0 ; i<m ; i++)
{
MIN=MAXINT;
for(int j=1 ; j<=m ; j++)
{
if(dis[j]<MIN && !flag0[j])
{
MIN=dis[j];
flag=j;
}
}
if(MIN==MAXINT)
break;
flag0[flag]=1;
for(int j=1 ; j<=m ; j++)
if(!flag0[j])//attention
dis[j]=min(dis[j],dis[flag]+num0[flag][j]);//各点到草儿家所需最短时间
}
}
int main()
{
int i,j,a,b,time,Min;
while(~scanf("%d%d%d",&T,&S,&D))
{
m=-1;
for(i=0 ; i<1050 ; i++)
for(j=0 ; j<=i ; j++)
if(i != j)
num0[i][j]=num0[j][i]=MAXINT;
else
num0[i][j]=0;//点与点之间所需时间初始化
for(i=0 ; i<T ; i++)
{
scanf("%d%d%d",&a,&b,&time);
if(time<num0[a][b])//因为a,b间不止一条路,选取时间最短的那条
num0[a][b]=num0[b][a]=time;
m=max(max(m,a),b);
}
for(i=0 ; i<S ; i++)
{
int s;
scanf("%d",&s);
num0[0][s]=num0[s][0]=0;
}
for(i=0 ; i<D ; i++)
scanf("%d",&num1[i]);
dijkstra();
Min=MAXINT;
for(i=0 ; i<D ; i++)
Min=min(Min,dis[num1[i]]);//想要到的地方中所需最小时间
printf("%d\n",Min);
}
return 0;
}