hdu 2066 一个人的旅行
http://acm.hdu.edu.cn/showproblem.php?pid=2066
接着有T行,每行有三个整数a,b,time,表示a,b城市之间的车程是time小时;(1=<(a,b)<=1000;a,b 之间可能有多条路)
接着的第T+1行有S个数,表示和草儿家相连的城市;
接着的第T+2行有D个数,表示草儿想去地方。
#include<iostream>
using namespace std;
#define INF 999999
int dis[1001],v[1001];
int map[1001][1001];
void dijkstra(int s,int n)
{
int i,j,k,min;
memset(v,0,sizeof(v));
for(i=1;i<=n;i++)
dis[i]=map[s][i];
v[s]=1;
for(i=2;i<=n;i++)
{
k=s;
min=INF;
for(j=1;j<=n;j++)
if(!v[j]&&dis[j]<min)
{
k=j;
min=dis[j];
}
v[k]=1;
for(j=1;j<=n;j++)
if(!v[j]&&map[k][j]<INF)
{
if(dis[j]>dis[k]+map[k][j])
dis[j]=dis[k]+map[k][j];
}
}
}
int main()
{
int t,s,d,a[1001],b[1001];
while(~scanf("%d%d%d",&t,&s,&d))
{
int j,i,aa,bb,p;
for(i=1;i<=1000;i++)
for(j=1;j<=1000;j++)
map[i][j]=INF;
while(t--)
{
scanf("%d%d%d",&aa,&bb,&p);
if(map[aa][bb]>p)
map[aa][bb]=map[bb][aa]=p;
}
for(i=1;i<=s;i++)
scanf("%d",&a[i]);
for(i=1;i<=d;i++)
scanf("%d",&b[i]);
int min=INF;
for(i=1;i<=s;i++)
{
dijkstra(a[i],1000);
for(j=1;j<=d;j++)
if(min>dis[b[j]])
min=dis[b[j]];
}
printf("%d\n",min);
}
return 0;
}