hdu 2066 一個人的旅行（SPFA算法）

輸入T，S，D，表示有T條邊，S個起點，D個終點；每條邊輸入兩個點及邊權，然後輸入起點和終點；本題關鍵是有多個起點，從而求最短距離不好求，可采取相應方法進行簡化，將每個起點與另外的一個點連接，使其邊權為0，這樣即可使起點變成一個；然後比較到每個終點的距離即可。參考代碼：

#include
#include
#include
#include
#define MAXN 10010
#define MAXM 20020
#define INF 0x3f3f3f3f
using namespace std;
int head[MAXN];
int mark[MAXN];
int dis[MAXN];
struct node{
	int from,to,val,next;
};
node edge[MAXM];
int num;
void getmap(int u,int v,int w)
{
	node e={u,v,w,head[u]};
	edge[num]=e;
	head[u]=num++;
}
void SPFA(int s)
{
	queueq;
	memset(mark,0,sizeof(mark));
	memset(dis,INF,sizeof(dis));
	q.push(s);
	while(!q.empty())
	{
		int top=q.front();
		q.pop();
		mark[s]=1;
		dis[s]=0;
		for(int i=head[top];i!=-1;i=edge[i].next)
		{
			int u=edge[i].to;
			if(dis[u]>dis[top]+edge[i].val)
			{
				dis[u]=dis[top]+edge[i].val;
				if(!mark[u])
				{
					mark[u]=1;
					q.push(u);
				}
			}
		}
	}
}
int main()
{
	int t,s,d,start,end;
	while(scanf(%d%d%d,&t,&s,&d)!=EOF)
	{
		memset(head,-1,sizeof(head));
		num=0;
		int m=INF;
		for(int i=0;i