hdu2066上海交通大学模板过的啊！.txt

数据结构中的单元最短路径算法的题目和源代码！其中所有的题目都能在PKU上找的到！

//单源最短路径！用上海交通大学模板过的！
#include<stdio.h>
#include<string.h>
const int MAXV=1005;
const int MAXE=504510;
const int INF=0x7fffffff;
typedef struct Edge
{
	int st;
	int ed;
	int distance;
}Edge;
Edge edge[MAXE];
int V,E,num,len,next[MAXE],ev[MAXE],ew[MAXE];
int value[MAXV],mk[MAXV],nbs[MAXV],ps[MAXV],heap[MAXV];
void update(int r)
{
	int q=ps[r],p=q>>1;
	while(p&&value[heap[p]]>value[r])
	{
		ps[heap[p]]=q;
		heap[q]=heap[p];
		q=p;
		p=q>>1;
	}
	heap[q]=r;
	ps[r]=q;
}
int getmin()
{
	int ret=heap[1],p=1,q=2,r=heap[len--];
	while(q<=len)
	{
		if(q<len&&value[heap[q+1]]<value[heap[q]])
			q++;
		if(value[heap[q]]<value[r])
		{
			ps[heap[q]]=p;
			heap[p]=heap[q];
			p=q;
			q=p<<1;
		}
		else
			break;
	}
	heap[p]=r;
	ps[r]=p;
	return ret;
}
//src表示源点 dst表示终点!
void Dijkstra(int src,int dst)
{
	int i,j,u,v;
	for(i=1;i<=V;i++)
	{
		value[i]=INF;
		mk[i]=ps[i]=0;
	}
	value[src]=0;
	heap[len=1]=src;
	ps[src]=1;
	while(!mk[dst])
	{
		if(len==0)
			return;
		u=getmin();
		mk[u]=1;
		for(j=nbs[u];j;j=next[j])
		{
			v=ev[j];
			if(!mk[v]&&value[u]+ew[j]<value[v])
			{
				if(ps[v]==0)
				{
					heap[++len]=v;
					ps[v]=len;
				}
				value[v]=value[u]+ew[j];
				update(v);
			}
		}
	}
}
int main()
{
	int i,u,v,w;
	int want[MAXV],ling[MAXV];
	int j,min,S,D,N;
	while(scanf("%d%d%d",&N,&S,&D)!=EOF)
	{
		memset(nbs,0,sizeof(nbs));
		num=0,min=INF,V=1000;
		for(i=1;i<=N;i++)
		{
			scanf("%d%d%d",&u,&v,&w);
			next[++num]=nbs[u];
			nbs[u]=num;
			ev[num]=v;
			ew[num]=w;

			next[++num]=nbs[v];
			nbs[v]=num;
			ev[num]=u;
			ew[num]=w;
		}
		for(i=1;i<=S;i++)
			scanf("%d",&ling[i]);
		for(i=1;i<=D;i++)
			scanf("%d",&want[i]);
		for(i=1;i<=S;i++)
		{
			Dijkstra(ling[i],V);
			for(j=1;j<=D;j++)
				if(min>value[want[j]])
					min=value[want[j]];
		}
		printf("%d\n",min);
	}
	return 0;
}
/*
6 2 3
1 3 5
1 4 7
2 8 12
3 8 4
4 9 12
9 10 2
1 2
8 9 10
 

9
*/