首先考虑分别求出在两个人最短路上的边,这个就是用 \(s\) 跑一遍最短路,\(t\) 跑一遍最短路,然后枚举边 \((u,v)\),如果满足 \((s\to u) + (u\to v)+(t\to v)=(s\to t)\) 那么说明有向边 \(u\to v\) 就是一条在最短路上的有向边。
处理后,注意到我们得到了两张 DAG,然后题意有点坑,实际上只要路径重合都算一起走,无论相反还是相遇,问题在于两个人不可能一会相反一会相遇,因此考虑在第一个人的 DAG 上做两次记忆化搜索,一次只允许相遇边,一次只允许相反边。
Code:
/*
========= Plozia =========
Author:Plozia
Problem:P2149 [SDOI2009] Elaxia的路线
Date:2022/10/5
========= Plozia =========
*/
#include <bits/stdc++.h>
typedef long long LL;
using std::queue;
using std::priority_queue;
const int MAXN = 1500 + 5, MAXM = 3e5 + 5;
int n, m, s1, t1, s2, t2, Head[MAXN], cntEdge = 1;
LL dis[2][2][MAXN], f[MAXN][2];
bool book[MAXN], vis1[MAXM << 1], vis2[MAXM << 1];
struct node { int To; LL val; int Next; } Edge[MAXM << 1];
struct pri { int x; LL dis; bool operator <(const pri &fir)const { return dis > fir.dis; } } ;
int Read()
{
int sum = 0, fh = 1; char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
return sum * fh;
}
void add(int x, int y, int z) { ++cntEdge; Edge[cntEdge] = (node){y, z, Head[x]}; Head[x] = cntEdge; }
LL Min(LL fir, LL sec) { return (fir < sec) ? fir : sec; }
LL Max(LL fir, LL sec) { return (fir > sec) ? fir : sec; }
void Dijkstra(int s, int who, int opt)
{
for (int i = 1; i <= n; ++i) book[i] = 0;
priority_queue <pri> q; q.push((pri){s, 0}); dis[who][opt][s] = 0;
while (!q.empty())
{
int x = q.top().x; q.pop(); if (book[x]) continue ; book[x] = 1;
for (int i = Head[x]; i; i = Edge[i].Next)
{
int u = Edge[i].To; if (book[u]) continue ;
if (dis[who][opt][u] > dis[who][opt][x] + Edge[i].val)
{
dis[who][opt][u] = dis[who][opt][x] + Edge[i].val;
q.push((pri){u, dis[who][opt][u]});
}
}
}
}
LL dfs(int now, int opt)
{
if (f[now][opt] != -1) return f[now][opt]; f[now][opt] = 0;
for (int i = Head[now]; i; i = Edge[i].Next)
{
int u = Edge[i].To; if (book[u] || !vis1[i]) continue ;
book[u] = 1; LL s = dfs(u, opt);
f[now][opt] = Max(f[now][opt], s + vis2[i ^ opt] * Edge[i].val); book[u] = 0;
}
return f[now][opt];
}
int main()
{
n = Read(), m = Read(); s1 = Read(), t1 = Read(), s2 = Read(), t2 = Read();
memset(dis, 0x3f, sizeof(dis));
for (int i = 1; i <= m; ++i) { int x = Read(), y = Read(), z = Read(); add(x, y, z); add(y, x, z); }
Dijkstra(s1, 0, 0); Dijkstra(t1, 0, 1); Dijkstra(s2, 1, 0); Dijkstra(t2, 1, 1);
for (int i = 2; i <= cntEdge; i += 2)
{
int x = Edge[i].To, y = Edge[i ^ 1].To;
if (dis[0][0][x] + Edge[i].val + dis[0][1][y] == dis[0][0][t1]) vis1[i ^ 1] = 1;
if (dis[0][1][x] + Edge[i].val + dis[0][0][y] == dis[0][0][t1]) vis1[i] = 1;
if (dis[1][0][x] + Edge[i].val + dis[1][1][y] == dis[1][0][t2]) vis2[i ^ 1] = 1;
if (dis[1][1][x] + Edge[i].val + dis[1][0][y] == dis[1][0][t2]) vis2[i] = 1;
}
for (int i = 1; i <= n; ++i) book[i] = 0;
memset(f, -1, sizeof(f)); book[s1] = 1; f[t1][0] = f[t1][1] = 0;
f[s1][0] = dfs(s1, 0), f[s1][1] = dfs(s1, 1);
LL ans = -1; for (int i = 1; i <= n; ++i) ans = Max(ans, Max(f[i][0], f[i][1])); printf("%lld\n", ans); return 0;
}
标签:opt,int,题解,Read,Edge,SDOI2009,now,Elaxia,dis
From: https://www.cnblogs.com/Plozia/p/16756999.html