LP2149 [SDOI2009]Elaxia的路线 [最短路/拓扑/结论/填坑]

Author Avatar
空気浮遊 2018年08月20日
  • 在其它设备中阅读本文章
  • dp
  • 最短路
  • 拓扑
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

坑 -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 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • May 2025 1
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 31
    • August 2018 18
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 281
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material