思路与算法

分别求A出发、到B、C出发、到D的四组最短距离。筛出同时位于两人最短路线中的点和边。正权下这些公共边按A距离严格递增，构成DAG；每个公共点可作起点计1，按距离排序做最长路节点数DP。任一原始目的地不可达时输出-1。

正确性说明

任一可行会合序列必须按同一顺序出现在双方最短路上。两个相邻会合点之间双方子路都是它们之间的最短路，故可替换为同时满足两人最短等式的公共子路。因此会合序列可包含在公共DAG的一条路上。反之公共路可接各人的最短前后缀，并用休息同步所有会合点，所以最长节点数可达且最优。

复杂度

建正反图O(N+M)，四次Dijkstra O((N+M)log(N+M))，排序O(NlogN)、DAG转移O(N+M)，总空间O(N+M)。距离可达约2.5×10^13，使用64位。

易错点

公共节点不一定从共同起点可达，DP应允许任何公共点起步。没有公共点答案0；任一行程无路才为-1。正权是按距离拓扑的依据。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using Edge = pair<int, long long>;
vector<long long> dij(int s, const vector<vector<Edge>> &g) {
    const long long INF = 1LL << 60;
    vector<long long> d(g.size(), INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                   greater<pair<long long, int>>>
        q;
    d[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        auto t = q.top();
        q.pop();
        if (t.first != d[t.second])
            continue;
        for (auto e : g[t.second])
            if (d[e.first] > t.first + e.second) {
                d[e.first] = t.first + e.second;
                q.push({d[e.first], e.first});
            }
    }
    return d;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<Edge>> g(n), h(n);
    vector<tuple<int, int, long long>> es;
    while (m--) {
        int a, b;
        long long w;
        cin >> a >> b >> w;
        --a;
        --b;
        g[a].push_back({b, w});
        h[b].push_back({a, w});
        es.emplace_back(a, b, w);
    }
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    --A;
    --B;
    --C;
    --D;
    auto a = dij(A, g), b = dij(B, h), c = dij(C, g), d = dij(D, h);
    if (a[B] == (1LL << 60) || c[D] == (1LL << 60)) {
        cout << -1 << '\n';
        return 0;
    }
    vector<int> ok(n), dp(n), ord(n);
    for (int i = 0; i < n; i++) {
        ok[i] = a[i] + b[i] == a[B] && c[i] + d[i] == c[D];
        dp[i] = ok[i];
    }
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int u, int v) {
        return a[u] < a[v];
    });
    int ans = 0;
    for (int u : ord) {
        ans = max(ans, dp[u]);
        if (!ok[u])
            continue;
        for (auto e : g[u])
            if (ok[e.first] && a[u] + e.second == a[e.first] && c[u] + e.second == c[e.first])
                dp[e.first] = max(dp[e.first], dp[u] + 1);
    }
    cout << ans << '\n';
}