题目

图论综合题。

首先我们需要求出所有在公共最短路上的边,可以用预处理出最短路长度,然后枚举每一条边,依次判断即可。然后把这些边建到一个新图里,跑DP就好了。

此题的关键就是求出在公共最短路上的边。

#include <bits/stdc++.h>
#define N 7001011
using namespace std;
int n, m, a, b, c, d, cnt, maxn, lin[N], cnt2, lin2[N], dis[5011][5011], vis[N], dp[N];
struct edg
{
    int from, to, nex, len;
    int boo;//表示该边是否同时在他们的最短路上。
} e[N], e2[N];
inline void add(int f, int t, int l)
{
    e[++cnt].from = f;
    e[cnt].to = t;
    e[cnt].len = l;
    e[cnt].nex = lin[f];
    lin[f] = cnt;
}
inline void add2(int f, int t, int l)
{
    e2[++cnt2].from = f;
    e2[cnt2].to = t;
    e2[cnt2].len = l;
    e2[cnt2].nex = lin2[f];
    lin2[f] = cnt2;
    vis[f] = vis[t] = 1;
}
void spfa(int s)
{
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++)
        dis[s][i] = 2147483647;
    queue <int> q;
    while (!q.empty()) q.pop();
    dis[s][s] = 0;
    q.push(s);
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        vis[cur] = 0;
        for (int i = lin[cur]; i; i = e[i].nex)
            if (dis[s][cur] + e[i].len < dis[s][e[i].to])
            {
                dis[s][e[i].to] = dis[s][cur] + e[i].len;
                if (!vis[e[i].to])
                    q.push(e[i].to), vis[e[i].to] = 1;
            }
    }
}
void init()
{
    scanf("%d%d", &n, &m);
    scanf("%d%d%d%d", &a, &b, &c, &d);
    for (int i = 1, a, b, c; i <= m; i++)
        scanf("%d%d%d", &a, &b, &c), add(a, b, c), add(b, a, c);
    spfa(a), spfa(b), spfa(c), spfa(d);
    memset(vis, 0, sizeof(vis));
    for (int j = 1; j <= n; j++)
        for (int i = lin[j]; i; i = e[i].nex)
        {
            int f = e[i].from, t = e[i].to;
            int l = e[i].len;
            if (dis[a][f] + l + dis[b][t] == dis[a][b])//说明此边在他们的公共路径上
            {
                if (dis[c][f] + l + dis[d][t] == dis[c][d]) add2(f, t, l);
                if (dis[d][f] + l + dis[c][t] == dis[c][d]) add2(t, f, l);
            }
        }
//  printf("%d", dis[1][6]);
}
int dfs(int now)
{
    if (dp[now]) return dp[now];
    for (int i = lin2[now]; i; i = e2[i].nex)
    {
        int to = e2[i].to;
        dp[now] = max(dp[now], e2[i].len + dfs(to));
    }
    return dp[now];
}
int main()
{
    init();//找到所有在公共最短路上的边
//  printf("%d %d %d\n", e2[1].from, e2[1].to, e2[1].len);
    for (int i = 1; i <= n; i++)
        dfs(i);
    for (int i = 1; i <= n; i++)
        maxn = max(maxn, dp[i]);
    printf("%d", maxn);//最后是0
    return 0;
}
/*
9 10
1 6 7 8
1 2 3
2 5 5
2 3 1
3 4 3
3 9 2
4 5 3
4 6 2
4 7 3
5 8 1
7 9 2
*/
02-12 11:20