BZOJ原题链接
洛谷原题链接
显然最长公共路径是最短路上的一条链。
我们可以把最短路经过的边看成有向边，那么组成的图就是一张\(DAG\)，这样题目要求的即是两张\(DAG\)重合部分中的最长链。
重合部分中的最长链可能是同向，可能是反向的，但不可能由反向边和同向边组成，否则就不是\(DAG\)了。
所以我们分别只保留重合部分的同向边、反向边，跑两次拓扑排序求最长链，在两者中取\(\max\)即可。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1510;
const int M = 2.5e6;
struct dd {
int x, D;
bool operator < (const dd &b) const { return D > b.D; }
};
int fi[N], di[M], ne[M], da[M], cfi[N], cdi[M], cne[M], cda[M], dis_1[N], dis_2[N], dis_3[N], dis_4[N], dis[N], ru[N], tq[N], l, x_1, y_1, x_2, y_2, lc, ma, n;
bool v[N];
priority_queue<dd>q;
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
inline void add(int x, int y, int z)
{
di[++l] = y;
da[l] = z;
ne[l] = fi[x];
fi[x] = l;
}
inline void add_c(int x, int y, int z)
{
cdi[++lc] = y;
cda[lc] = z;
cne[lc] = cfi[x];
cfi[x] = lc;
ru[y]++;
}
inline int maxn(int x, int y){ return x > y ? x : y; }
void dij(int st, int dis[])
{
memset(v, 0, sizeof(v));
int i, x, y;
dis[st] = 0;
q.push((dd){st, 0});
while (!q.empty())
{
x = q.top().x;
q.pop();
if (v[x])
continue;
v[x] = 1;
for (i = fi[x]; i; i = ne[i])
if (dis[y = di[i]] >= dis[x] + da[i])
q.push((dd){y, dis[y] = dis[x] + da[i]});
}
}
void topsort()
{
int i, x, y, head = 0, tail = 0;
for (i = 1; i <= n; i++)
if (!ru[i])
tq[++tail] = i;
while (head ^ tail)
{
x = tq[++head];
ma = maxn(ma, dis[x]);
for (i = cfi[x]; i; i = cne[i])
{
y = cdi[i];
dis[y] = maxn(dis[y], dis[x] + cda[i]);
if (!(--ru[y]))
tq[++tail] = y;
}
}
}
int main()
{
int i, j, m, x, y, z;
n = re();
m = re();
x_1 = re();
y_1 = re();
x_2 = re();
y_2 = re();
for (i = 1; i <= m; i++)
{
x = re();
y = re();
z = re();
add(x, y, z);
add(y, x, z);
}
memset(dis_1, 60, sizeof(dis_1));
memset(dis_2, 60, sizeof(dis_2));
memset(dis_3, 60, sizeof(dis_3));
memset(dis_4, 60, sizeof(dis_4));
dij(x_1, dis_1);
dij(y_1, dis_2);
dij(x_2, dis_3);
dij(y_2, dis_4);
for (i = 1; i <= n; i++)
for (j = fi[i]; j; j = ne[j])
if (!((dis_1[i] + da[j] + dis_2[di[j]]) ^ dis_1[y_1]) && !((dis_3[i] + da[j] + dis_4[di[j]]) ^ dis_3[y_2]))
add_c(i, di[j], da[j]);
topsort();
memset(cfi, 0, sizeof(fi));
memset(dis, 0, sizeof(dis));
lc = 0;
for (i = 1; i <= n; i++)
for (j = fi[i]; j; j = ne[j])
if (!((dis_1[i] + da[j] + dis_2[di[j]]) ^ dis_1[y_1]) && !((dis_4[i] + da[j] + dis_3[di[j]]) ^ dis_3[y_2]))
add_c(i, di[j], da[j]);
topsort();
printf("%d", ma);
return 0;
}