题解 P2149 【[SDOI2009]Elaxia的路线】
其实楼下几位给的判定“某一条边在不在最短路中的方法”确实不错
即根据最短路的性质，若dis(s,i)+len(i,j)+dis(j,t)=dis(s,t)，则边(i,j)在s->t的最短路上
但是我常用的是另外一种方法，效率也不错
这种方法类似于dp中，计算出所有状态，最后要打印解的时候的“顺着最终状态找决策”
这种方法只用spfa两遍，不过仍然要倒序寻找两遍
即从x1点spfa一遍之后，从y1点倒序寻找，对于所有的y1的相邻节点v，若dist[v] + len(v,y1) = dist[y1]，则边(v,y1)在最短路上，点v在最短路上
然后把v点推入队列，用bfs的方式对于所有的“在最短路上的点”都进行这样的操作，这样就求出了所有在x1->y1的最短路上的边，可以用邻接矩阵保存，方便查找
然后从x2点spfa之后，用相同的方式找x2->y2的最短路径上的所有边，如果有边(u,v)同时在x1->y1和x2->y2的最短路上出现了
那么在新的“最短路图”中构造一条弧<u,v>，其中dist[u] < dist[v]，这里的dist可以取“从x1开始spfa的dist”或者是“从x2开始spfa的dist”中的任意一个，但是肯定不能两个混着用啦。。。
说的不是很清楚，详见代码，重复代码比较多，所以看起来比较长，实际上还是很好理解的。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 1502, MAXM = 1125000;
const int INF = 0x3f3f3f3f;
int n,m,x1,my_y1,x2,y2;
struct Myque {
int arr[MAXN], head, tail;
Myque() { clear(); }
void clear() { head = tail = 0; }
void push_back( int num ) { arr[tail] = num; if( ++tail == MAXN ) tail = 0; }
void push_front( int num ) { if( --head == -1 ) head = MAXN-1; arr[head] = num; }
void pop() { if( ++head == MAXN ) head = 0; }
int front() { return arr[head]; }
bool empty() { return head == tail; }
};
struct Graph {
int head[MAXN], to[MAXM<<1], nxt[MAXM<<1], w[MAXM<<1], idx;
Graph() { idx = 0; memset( head, -1, sizeof(head) ); }
void addedge( int u, int v, int l ) {
to[idx] = v; w[idx] = l; nxt[idx] = head[u]; head[u] = idx; ++idx;
}
bool inq[MAXN]; Myque q; int dist[MAXN];
void spfa( int s ) {
memset( dist, 0x3f, sizeof(dist) ); dist[s] = 0;
memset( inq, false, sizeof(inq) ); inq[s] = true; q.push_back(s);
while( !q.empty() ) {
int u = q.front(); q.pop(); inq[u] = false;
for( int e = head[u]; ~e; e = nxt[e] ) {
int v = to[e];
if( dist[v] > dist[u] + w[e] ) {
dist[v] = dist[u] + w[e];
if( !inq[v] ) { inq[v] = true;
if( dist[v] <= q.front() ) q.push_front(v);
else q.push_back(v);
}
}
}
}
}
}origin,sp;
namespace Toposort {
int in[MAXN]; Myque q; Myque rstq;
void init() { memset( in, 0, sizeof(in) ); }
void topo( const Graph &g ) {
for( int i = 1; i <= n; ++i ) if( !in[i] ) q.push_back(i);
while( !q.empty() ) {
int u = q.front(); q.pop(); rstq.push_back(u);
for( int e = g.head[u]; ~e; e = g.nxt[e] ) {
int v = g.to[e];
if( --in[v] == 0 ) q.push_back(v);
}
}
}
int dist[MAXN];
int dpf( const Graph &g ) {
memset( dist, 0, sizeof(dist) ); int ans = 0;
while( !rstq.empty() ) {
int u = rstq.front(); rstq.pop(); ans = max( ans, dist[u] );
for( int e = g.head[u]; ~e; e = g.nxt[e] ) {
int v = g.to[e], w = g.w[e];
dist[v] = max( dist[v], dist[u] + w );
}
}
return ans;
}
}
using Toposort::in;
using Toposort::topo;
using Toposort::dpf;
namespace MarkPath {
int adj[MAXN][MAXN]; Myque q; bool vis[MAXN];
void mark_path( const Graph &g, int t ) {
memset( adj, 0, sizeof(adj) ); q.push_back(t);
memset( vis, false, sizeof(vis) ); vis[t] = true;
while( !q.empty() ) {
int u = q.front(); q.pop();
for( int e = g.head[u]; ~e; e = g.nxt[e] ) {
int v = g.to[e], w = g.w[e];
if( g.dist[v] == g.dist[u] - w ) {
adj[u][v] = adj[v][u] = w;
if( !vis[v] ) {
vis[v] = true; q.push_back(v);
}
}
}
}
}
void mark_path_2( const Graph &g, int t, Graph &obj ) {
memset( vis, false, sizeof(vis) ); vis[t] = true;
q.push_back(t); Toposort::init();
while( !q.empty() ) {
int u = q.front(); q.pop();
for( int e = g.head[u]; ~e; e = g.nxt[e] ) {
int v = g.to[e], w = g.w[e];
if( g.dist[v] == g.dist[u] - w ) {
if( !vis[v] ) {
vis[v] = true; q.push_back(v);
}
if( adj[v][u] ) {
obj.addedge(v,u,w); in[u]++;
}
}
}
}
}
}
using MarkPath::mark_path;
using MarkPath::adj;
using MarkPath::mark_path_2;
int main() {
scanf( "%d%d%d%d%d%d", &n, &m, &x1, &my_y1, &x2, &y2 );
for( int i = 0; i < m; ++i ) {
int u,v,l; scanf( "%d%d%d", &u, &v, &l );
origin.addedge(u,v,l); origin.addedge(v,u,l);
}
origin.spfa(x1); mark_path(origin,my_y1);
origin.spfa(x2); mark_path_2(origin,y2,sp);
topo(sp); printf( "%d\n", dpf(sp) );
return 0;
}