题目地址：洛谷：【P2149】[SDOI2009]Elaxia的路线 – 洛谷、BZOJ：Problem 1880. — [Sdoi2009]Elaxia的路线

题目描述

最近，Elaxia和w**的关系特别好，他们很想整天在一起，但是大学的学习太紧张了，他们 必须合理地安排两个人在一起的时间。
Elaxia和w**每天都要奔波于宿舍和实验室之间，他们 希望在节约时间的前提下，一起走的时间尽可能的长。
现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图：地图上有N个路 口，M条路，经过每条路都需要一定的时间。 具体地说，就是要求无向图中，两对点间最短路的最长公共路径。

输入输出格式

输入格式：
第一行：两个整数N和M（含义如题目描述）。
第二行：四个整数x1、y1、x2、y2（1 ≤ x1 ≤ N，1 ≤ y1 ≤ N，1 ≤ x2 ≤ N，1 ≤ y2 ≤ N），分别表示Elaxia的宿舍和实验室及w**的宿舍和实验室的标号（两对点分别 x1,y1和x2,y2）。
接下来M行：每行三个整数，u、v、l（1 ≤ u ≤ N，1 ≤ v ≤ N，1 ≤ l ≤ 10000），表 u和v之间有一条路，经过这条路所需要的时间为l。

输出格式：
一行，一个整数，表示每天两人在一起的时间（即最长公共路径的长度）

输入输出样例

输入样例#1：

9 10
1 6 7 8
1 2 1
2 5 2
2 3 3
3 4 2
3 9 5
4 5 3
4 6 4
4 7 2
5 8 1
7 9 1

输出样例#1：

3

说明

对于30%的数据，N ≤ 100；
对于60%的数据，N ≤ 1000；
对于100%的数据，N ≤ 1500，输入数据保证没有重边和自环。

题解

首先我们要发现一个结论：两条最短路的最长公共链一定可以是连续的一条。如果有两段公共链，我们可以把中间断开的一段合并成一条链，合并后的答案显然更优。
因此我们只需要找到在两个点对最短路中公共部分的最长链即可。但是如何找到两个点之间所有的最短路中的公共部分是个问题。我们可以考虑分别处理出最短路并找边交集，但是我们有更优美的做法。如果一条边两端到最短路的端点的最短路距离和加上该边边权等于最短路长，则可以断定该边在最短路上。我们遍历边并且按照最短路的方向建出有向图，在有向图上拓扑求最长链即可。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cctype>
#include <cstring>

#include <vector>
#include <queue>
#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 1505;

struct Edge {
    int to, w;
};
std::vector<Edge> gra[MAXN], gran[MAXN];
int deg[MAXN];

int n, m;

int d1[MAXN], d2[MAXN], d3[MAXN], d4[MAXN];
bool inque[MAXN];

inline void spfa(int s, int dis[]) {
    memset(dis, 0x3f, sizeof(int) * MAXN);
    std::queue<int> que;
    dis[s] = 0; inque[s] = true; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop(); inque[u] = false;
        for(int i = 0; i < gra[u].size(); i++) {
            int v = gra[u][i].to;
            if(dis[v] > dis[u] + gra[u][i].w) {
                dis[v] = dis[u] + gra[u][i].w;
                if(!inque[v]) {
                    inque[v] = true;
                    que.push(v);
                }
            }
        }
    }
}

int dp[MAXN];

inline int toposort() {
    int ans = 0;
    std::queue<int> que;
    for(int i = 1; i <= n; i++) {
        if(!deg[i]) {
            que.push(i);
        }
    }
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = 0; i < gran[u].size(); i++) {
            int v = gran[u][i].to;
            dp[v] = std::max(dp[v], dp[u] + gran[u][i].w);
            ans = std::max(ans, dp[v]);
            deg[v]--;
            if(!deg[v]) {
                que.push(v);
            }
        }
    }
    return ans;
}

struct Edge1 {
    int u, v, l;
};
std::vector<Edge1> edges;

int s1, t1, s2, t2, u, v, l;

int main() {
    n = readint(); m = readint();
    s1 = readint(); t1 = readint(); s2 = readint(); t2 = readint();
    edges.push_back(Edge1 {0, 0, 0});
    for(int i = 1; i <= m; i++) {
        u = readint(); v = readint(); l = readint();
        edges.push_back(Edge1 {u, v, l});
        gra[u].push_back(Edge {v, l});
        gra[v].push_back(Edge {u, l});
    }
    spfa(s1, d1); spfa(t1, d2);
    spfa(s2, d3); spfa(t2, d4);
    for(int i = 1; i <= m; i++) {
        int dt1 = std::min(d1[edges[i].u], d1[edges[i].v]) 
                + std::min(d2[edges[i].u], d2[edges[i].v]) + edges[i].l,
            dt2 = std::min(d3[edges[i].u], d3[edges[i].v]) 
                + std::min(d4[edges[i].u], d4[edges[i].v]) + edges[i].l;
        if(dt1 == d1[t1] && dt2 == d3[t2]) {
            if(d1[edges[i].u] < d1[edges[i].v]) {
                gran[edges[i].u].push_back(Edge {edges[i].v, edges[i].l});
                deg[edges[i].v]++;
            } else {
                gran[edges[i].v].push_back(Edge {edges[i].u, edges[i].l});
                deg[edges[i].u]++;
            }
        }
    }
    printf("%d", toposort());
    return 0;
}