题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1880

题目链接：https://www.luogu.com.cn/problem/P2149

题意

求无向图中，两对点间最短路的最长公共路径。

做法

这应该不是标算（乱搞踩标算

• 假如两对点分别是$(a,b)$和$(c,d)$，要求$a$到$b$的最短路和$c$到$d$的最短路的最长公共路径。
• 首先SPFA（其实有时候挺好用的）求出$a$到$b$的最短路，然后标记出该图中所有满足$dis(u) + w(u,v) = dis(v)$并且在$a$到$b$的最短路径上的有向边$(u,v)$。
• 构成一个从$a$到$b$的最短路径图，是一个DAG。
• 然后同理SPFA求$c$到$d$的最短路，同理找出该图中所有满足$dis(u) + w(u,v) = dis(v)$并且在$c$到$d$的最短路径上的有向边$(u,v)$。这一次连边重新建图：如果这条有向边$(u,v)$被标记过，边权设为该边原本边权。否则边权为0，并记录下来这条边原本的边权（后面有用）。在这个新建的有向无环图上用拓扑排序DP统计答案。
• 然后把上面重新建的图反过来（这是我这个题解的特色）。原来边权为0的改为原本的边权（上面记录的这个时候用到），不为0的改为0，在这个图上再一次用拓扑排序DP统计答案。
• 答案为两次拓扑排序的最大值。

比较有价值的部分是我的建图，可能这个题不是正解，但是我的两点间最短路径图的求法是我写着博客的主要原因，具体看代码。

代码

#include 
#include 
#include 
#include 
#define Re register
using namespace std;
inline int read() {
    Re int x = 0;
    char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}
const int maxN = 1505, maxM = 300005;
int N, M, A, B, C, D, f[maxN];
struct Edge1 {
    int nxt, to, dis;
} e[maxM << 1];
int head[maxN], cnte = 1;
struct Edge2 {
    int nxt, to, dis, from;
} ee[maxM << 1];
int hhead[maxN], ccnte = 1;
inline void add_Edge(int i, int j, int k) {
    e[++cnte].nxt = head[i];
    e[cnte].dis = k;
    e[cnte].to = j;
    head[i] = cnte;
}
inline void add_edge(int i, int j, int k) {
    ee[++ccnte].dis = k;
    ee[ccnte].nxt = hhead[i];
    ee[ccnte].to = j;
    ee[ccnte].from = i;
    hhead[i] = ccnte;
}
int dis[maxN];
bool vis[maxN], is[maxN], have[maxN][maxN];
void SPFA(int S) {
    queue<int> Q;
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    vis[S] = true, Q.push(S), dis[S] = 0;
    while (!Q.empty()) {
        Re int u = Q.front();
        Q.pop();
        vis[u] = false;
        for (Re int v, i = head[u]; i; i = e[i].nxt) {
            if (dis[v = e[i].to] > dis[u] + e[i].dis) {
                dis[v] = dis[u] + e[i].dis;
                if (!vis[v]) 
                    Q.push(v), vis[v] = true;
            }
        }
    }
}
//第一次求两点之间的最短路径图 
int dfs1(int u, int S, int T, int len) { 
    vis[u] = true;
    if (u == T && len == dis[T]) //如果能到达终点并且是最短路就返回1 
        return is[u] = true;
    Re bool flag = false;
    for (Re int i = head[u]; i; i = e[i].nxt) {
        Re int v = e[i].to;
        if (dis[u] + e[i].dis == dis[v]) {
/*------保证每一个点最多访问一次，复杂度在这里降为O(n)------*/    
            if (vis[v] && is[v]) {
                flag = have[u][v] = true;                
            }
            else if (vis[v]) continue;
/*---------------------接应上面分割线-----------------------*/
            else if (dfs1(v, S, T, len + e[i].dis)) 
                flag = have[u][v] = true;
        }
    }
    return is[u] = flag;
}
int ind[maxN], W[maxM];
int dfs2(int u, int S, int T, int len) {
    vis[u] = true;
    if (u == T && len == dis[T]) 
        return is[u] = true;
    Re bool flag = false;
    for (Re int i = head[u]; i; i = e[i].nxt) {
        Re int v = e[i].to;
        if (dis[u] + e[i].dis == dis[v]) {
            if (vis[v] && is[v]) {
                flag = true;
                if (have[u][v]) 
                    add_edge(u, v, e[i].dis), ++ind[v];            
                else {
                    add_edge(u, v, 0), ++ind[v];
                    if (have[v][u])
                        W[ccnte] = e[i].dis;    //记录原本的边            
                }
            }
            else if (vis[v]) continue;
            else if (dfs2(v, S, T, len + e[i].dis)) {
                flag = true;
                if (have[u][v]) 
                    add_edge(u, v, e[i].dis), ++ind[v];            
                else {
                    add_edge(u, v, 0), ++ind[v];
                    if (have[v][u]) 
                        W[ccnte] = e[i].dis;    //记录原本的边                    
                }
        
            }
        }
    }
    return is[u] = flag;
}
void DP() {
    memset(f, 0, sizeof(f));
    queue<int> Q;
    for (int i = 1; i <= N; ++i) {
        if (!ind[i]) Q.push(i);    
    } 
    while (!Q.empty()) {
        Re int u = Q.front();
        Q.pop();
        for (int i = hhead[u]; i; i = ee[i].nxt) {
            Re int v = ee[i].to;
            f[v] = max(f[v], f[u] + ee[i].dis);
            --ind[v];
            if (!ind[v]) Q.push(v);
        }
    }
}
int main() {
    N = read(), M = read();
    A = read(), B = read(), C = read(), D = read();
    for (Re int i = 1; i <= M; ++i) {
        Re int u, v, w;
        u = read(), v = read(), w = read();
        add_Edge(u, v, w), add_Edge(v, u, w);
    }
    SPFA(A);
    memset(vis, 0, sizeof(vis));
    dfs1(A, A, B, 0);
    SPFA(C);
    memset(vis, 0, sizeof(vis));
    memset(is, 0, sizeof(is));
    dfs2(C, C, D, 0);
    DP();
    memset(ind, 0, sizeof(ind));
    int tmp = f[D];
    /*------------------------------*/
    //蒟蒻我今天才知道原来清除一个图只需要把head数组和cnte初始化就好了
    //正是利用了这个，才能如此方便的把图反过来，这得感谢Universal OJ群里的热心群友回答我的问题 
    memset(hhead, 0, sizeof(hhead));
    int k = ccnte;
    ccnte = 1;
    /*------------------------------*/
    for (Re int i = 2; i <= k; ++i) {
        Re int u = ee[i].from, v = ee[i].to, w = W[i];
        add_edge(v, u, w);
        ++ind[u];
    }
    DP();
    tmp = max(tmp, f[C]);
    printf("%d\n", tmp);
    return 0;//完结撒花~ 
}