我用邻接表建了无向图，利用spfa算法求了两次最短路:spfa(1,n)和spfa(n,1)，在求完第一次最短路后，将走过的路径全部删除。但是，总是无情的wa，代码如下，求真相。。。
#include <iostream>
#include <queue>
using namespace std;

const int MAXN = 1000 + 10;
const int MAXM = 50000 + 10;
const int INF = 99999999;
int dis[MAXN];				// dis[i]：从起点s到点i的费用
int p[MAXN];				// p[v] = e：到达点v的边的编号是e
int adj[MAXN];				// adj[u] = k：从点u出发的边的编号为k
bool inq[MAXN];				// inq[u]：点u是否在队列中
bool vis[MAXM];				// vis[k]：边k是否访问过

struct EDGE
{
	int u;
	int v;
	int cost;	
	int next;
};

EDGE map[MAXM];
int n, m;					
int e;						// 边的总数目
queue<int> q;

// 添加边 u-->v：权为cost
void Add(int u, int v, int cost)
{
	map[e].u = u;
	map[e].v = v;
	map[e].cost = cost;
	map[e].next = adj[u];
	adj[u] = e;
	e++;		
}

// 求s到t的最短路
int Spfa(int s, int t)
{
	int u, v, k;

	memset(inq, false, sizeof(inq));
	
	memset(p, -1, sizeof(p));
	for (int i=1; i<n+1; ++i)
	{
		dis[i] = INF;
	}
	
	q.push(s);
	inq[s] = true;
	dis[s] = 0;
	
	while (!q.empty())
	{
		u = q.front();
		q.pop();
		inq[u] = false;
		// 遍历从点u出发的边
		for (k=adj[u]; k!=-1; k=map[k].next)
		{
			v = map[k].v;
			// 更新从点s到点v的最短路
			if (!vis[k] && (dis[v] > dis[u]+map[k].cost))
			{
				dis[v] = dis[u]+map[k].cost;
				p[v] = k;
				if (!inq[v])
				{
					inq[v] = true;
					q.push(v); 
				}
			}
		}
	}

	// 过河拆桥，把走过的路全都删掉
	for (k=p[t]; k!=-1; k=p[map[k].u])
	{
		vis[k] = vis[k^1] = true;
	}
	
	return dis[t];
}

void Init(void)
{
	int u, v, w;
	memset(vis, false, sizeof(vis));
	memset(adj,-1,sizeof(adj));
	e = 0;									// 初始化边的数目为0
	
	scanf("%d%d", &n, &m);
	for (int i=1; i<=m; ++i)
	{
		scanf("%d%d%d", &u, &v, &w);
		Add(u, v, w);
		Add(v, u, w);
	}
}

int main()
{
	// 初始化数据，并建图
	Init();

	cout << (Spfa(1, n)+Spfa(1, n)) << endl;
	return 0;
}

• Re : (48) totop 2011-09-24 09:10:07
• Re:用spfa求两次最短路，如下： (23) zetrain 2011-10-07 20:12:05
• Re:用spfa求两次最短路，如下： (55) dingjian0312 2011-12-14 19:48:58
• Re:用spfa求两次最短路，如下： (17) wll969 2012-01-15 14:51:15
  • Re:用spfa求两次最短路，如下： (53) ajige 2012-03-14 21:38:17