学步园

此题目,就是一定要注意建双路边,而且因为不知道有多少个顶点,所以开始的时候就要建最多的情况.也就是1005(习惯性的多出几个咯),然后就是一个起点,对应的多个终点的两重循环就好,其实还是比较简单的.

贴出代码:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define inf 0x3fffffff

int M,S,D;//M represents the number of edges,S stands for the number of the beginning point,and D represents the number of destination;
int visit[1005];
int dis[1005];
int map[1005][1005];
int sta[1005];
int des[1005];

int dijkstra(int st)
{
	for(int i=1;i<=1005;i++)
		dis[i]=inf;
	dis[st]=0;
	for(int j=1;j<=1005;j++)
	{
		int t=inf,pos;
		for(i=1;i<=1005;i++)
		{
			if(!visit[i]&&t>dis[i])
			{
				t=dis[i];
				pos=i;
			}
		}
		visit[pos]=i;
		for(i=1;i<=1005;i++)
		{
			if(!visit[i]&&dis[i]>dis[pos]+map[pos][i]&&map[pos][i]!=0x3f3f3f3f)
			{
				dis[i]=dis[pos]+map[pos][i];
			}
		}
	}
	int min=inf;
	for(int k=1;k<=D;k++)
	{
		if(min>dis[des[k]])
		{
			min=dis[des[k]];
		}
	}
	return min;
}

int main()
{
	while(scanf("%d%d%d",&M,&S,&D)!=EOF)
	{
		int a,b,time;
		memset(map,0x3f,sizeof(map));
		for(int i=1;i<=M;i++)
		{
			scanf("%d%d%d",&a,&b,&time);
			if(time<map[a][b])
			{
				map[a][b]=time;
				map[b][a]=time;
			}
		}
		for(int j=1;j<=S;j++)
		{
			scanf("%d",&sta[j]);
		}
		for(i=1;i<=D;i++)	
		{
			scanf("%d",&des[i]);
		}
		int t=inf;
		for(j=1;j<=S;j++)
		{
			memset(visit,0,sizeof(visit));
			int ans=dijkstra(sta[j]);
			if(t>ans)
			{
				t=ans;
			}
		}
		printf("%d\n",t);
	}
	return 0;
}