#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
#define maxv 10000
#define maxe 200000
#define INF 0x3f3f3f3f

int head[maxv],nn;//邻接表

int dist_s[maxv];//SPFA_s
int dist_e[maxv];//SPFA_e
bool visit[maxv];//SPFA

struct node//邻接表
{
	int to;
	int next;
	int cost;
}E[maxe];

void addEdge(int a,int b,int pp)//邻接表
{
	E[nn].cost=pp;
	E[nn].to=b;
	E[nn].next=head[a];
	head[a]=nn++;
}

void SPFA_s(int start)
{
	memset(dist_s,INF,sizeof(dist_s));//初始化distance数组
	memset(visit,0,sizeof(visit));//初始化distance数组
	dist_s[start]=0;
	queue<int>Q;
	//清空queue
	while(!Q.empty()) Q.pop();
	//
	Q.push(start);
	visit[start]=1;
	while(!Q.empty())
	{
		int u=Q.front(); Q.pop();visit[u]=0;
		for (int i=head[u];i!=-1;i=E[i].next)
		{
			if (dist_s[E[i].to]>dist_s[u]+E[i].cost)
			{
				dist_s[E[i].to]=dist_s[u]+E[i].cost;
				if (visit[E[i].to]==0)
					{Q.push(E[i].to);visit[E[i].to]=1;}
			}
		}
	}
}


void SPFA_e(int end)
{
	memset(dist_e,INF,sizeof(dist_e));//初始化distance数组
	memset(visit,0,sizeof(visit));//初始化distance数组
	dist_e[end]=0;
	queue<int>Q;
	//清空queue
	while(!Q.empty()) Q.pop();
	//
	Q.push(end);
	visit[end]=1;
	while(!Q.empty())
	{
		int u=Q.front(); Q.pop();visit[u]=0;
		for (int i=head[u];i!=-1;i=E[i].next)
		{
			if (dist_e[E[i].to]>dist_e[u]+E[i].cost)
			{
				dist_e[E[i].to]=dist_e[u]+E[i].cost;
				if (visit[E[i].to]==0)
					{Q.push(E[i].to);visit[E[i].to]=1;}
			}
		}
	}
}

int main()
{
	int N,R,A,B;
	int D;
	scanf("%d %d",&N,&R);
	//初始化head数组
	memset(head,-1,sizeof(head));
	nn=1;
	//读入,建图
	for (int i=1;i<=R;i++)
	{
		scanf("%d %d %d",&A,&B,&D);
		addEdge(A,B,D);//双向正边
		addEdge(B,A,D);
	}
	//SPFA
	SPFA_s(1);
	SPFA_e(N);
	//枚举每一条边
	int ans=INF;
	for (int i=1;i<=N;i++)
		for (int j=head[i];j!=-1;j=E[j].next)
		{
			int temp=dist_s[i]+E[j].cost+dist_e[E[j].to];//temp=s->i+i->j+j->e
			if (temp<ans&&temp>dist_s[N])//取大于最短路的最小值
				ans=temp;
		}
	//输出
	printf("%d\n",ans);
	return 0;
}

• Re:spfa求双向最短路再枚举每一条边的方法wa了 贴代码求解 (30) cstdlib 2014-08-06 19:06:42