坑 -1

Problem

无向图上给两对点
找出两对点最短路的最长公共路径

$n\leq 1500$

Solution

处理出同在两点间最短路上的边

大力四遍最短路

然后在有向连通块上做一个小小的拓扑序 dp 就行了

Code

// Code by ajcxsu
// Problem: elaxia

#include<bits/stdc++.h>
using namespace std;

const int N=1510, M=N*N;
int h[N], to[M], nexp[M], W[M], in[N], p=1;
inline void ins(int a, int b, int w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, in[b]++, p++; }
struct Edge { int u, v, w; } e[M];

int d1[N], d2[N], d3[N], d4[N];
bool S[N];
int n, m, a, b, c, d;
void dij(int s, int dist[]) {
    memset(dist, 0x3f, sizeof(d1)), memset(S, 0, sizeof(S));
    dist[s]=0;
    int u=0;
    for(int i=1;i<=n;i++) {
        u=0;
        for(int j=1;j<=n;j++) if(!S[j] && dist[j]<dist[u]) u=j;
        S[u]=1;
        for(int uu=h[u];uu;uu=nexp[uu])
            if(!S[to[uu]] && dist[to[uu]]>dist[u]+W[uu])
                dist[to[uu]]=dist[u]+W[uu];
    }
    return;
}

bool vis[N];
int f[N];
int dfs(int x) {
    if(f[x]!=-1) return f[x];
    f[x]=0;
    for(int u=h[x];u;u=nexp[u])
        f[x]=max(f[x], dfs(to[u])+W[u]);
    return f[x];
}

int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m>>a>>b>>c>>d;
    int u, v, w;
    for(int i=0;i<m;i++) cin>>u>>v>>w, ins(u, v, w), ins(v, u, w), e[i]={u, v, w};
    dij(a, d1), dij(b, d2), dij(c, d3), dij(d, d4), memset(h, 0, sizeof(h)), p=1;
    memset(in, 0, sizeof(in));
    for(int i=0;i<m;i++) {
        u=e[i].u, v=e[i].v, w=e[i].w;
        if(d1[u]>d1[v]) swap(u, v);
        if(d1[u]+w+d2[v]!=d1[b]) continue;
        if(d3[u]>d3[v]) swap(u, v);
        if(d3[u]+w+d4[v]!=d3[d]) continue;
        ins(u, v, w);
    }
    memset(f, -1, sizeof(f));
    int ans=0;
    for(int i=1;i<=n;i++)
        if(!in[i]) ans=max(ans, dfs(i));
    cout<<ans<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/elaxia.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆