dijkstra 模板

Input

输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个；

接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time分钟；(1=<(a,b)<=1000;a,b 之间可能有多条路)

接着的第T+1行有S个数，表示和草儿家相连的城市；

接着的第T+2行有D个数，表示草儿想去地方。

Output

输出ZJB能去某个喜欢的城市的最短时间，如都不能到达，输出-1。

#include<stdio.h>
#include<string.h>

int map[1010][1010];
int ss[1010],dd[1010];
int d[1010],f[1010];
int N;

void dijkstra(int a)
{
	int i,j,k;
	memset(f,0,sizeof(f));
	for(i=1;i<=N;i++)
		d[i]=map[a][i];
	f[a]=1;
	for(i=1;i<N;i++)
	{
		int min=0x3f3f3f3f;
		for(j=1;j<=N;j++)
			if(d[j]<min && f[j]==0){
				min=d[j],k=j;
			}
		f[k]=1;
		for(j=1;j<=N;j++)
			if(d[k]+map[k][j]<d[j])
				d[j]=d[k]+map[k][j];
	}
}
int main()
{
	int t,s,e;
	while(~scanf("%d%d%d",&t,&s,&e))
	{
		int i,j,k;
		N=0;
		for(i=0;i<1010;i++)
			for(j=0;j<1010;++j)
				if(i==j) map[i][j]=0;
				else map[i][j]=0x3f3f3f3f;
		while(t--)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			if(a>N) N=a;
			if(b>N) N=b;
			if(map[a][b]>c) map[a][b]=c,map[b][a]=c;
		}
		for(i=0;i<s;++i)
			scanf("%d",&ss[i]);
		for(i=0;i<e;++i)
			scanf("%d",&dd[i]);
		int min=0x3f3f3f3f;
		for(i=0;i<s;++i)
		{
			dijkstra(ss[i]);
			for(j=0;j<e;j++)
				if(d[dd[j]]<min)
					min=d[dd[j]];
		}
		if(min==0x3f3f3f3f)
			printf("-1\n");
		else
			printf("%d\n",min);
	}
}