【图论经典题目讲解】洛谷 P2149 Elaxia的路线

P2149 Elaxia的路线

$\mathrm{Description}$

给定 $n$ 个点，$m$ 条边的无向图，求 $2$ 个点对间最短路的最长公共路径

$\mathrm{Solution}$

最短路有可能不唯一，所以公共路径的长度就有可能不同。

将 $2$ 条最短路都会经过的边（包括同向和异向）记录出来，并建立 $1$ 个新图，那么由于最短路（可以看做一条链）一定不会走环，故新图必定是一个 有向无环图 （简称 $\mathrm{DAG}$），而 $\mathrm{DAG}$ 图上就可以跑 DP 来求解最长链，由于找出的是 $2$ 条最短路都经过的边，所以最长链其实就是 $2$ 条最短路的最长公共路径。

故，该问题得以解决。

$Code$

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int SIZE = 1e6 + 10;

int N, M;
int X1, Y1, X2, Y2;
int h[SIZE], hs[SIZE], e[SIZE], ne[SIZE], w[SIZE], idx;
int D[4][SIZE], Vis[SIZE], in[SIZE], q[SIZE], hh, tt = -1;
int F[SIZE];

void add(int h[], int a, int b, int c)
{
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

void Dijkstra(int Start, int dist[])
{
	for (int i = 1; i <= N; i ++)
		dist[i] = 1e18, Vis[i] = 0;
	priority_queue<PII, vector<PII>, greater<PII>> Heap;
	Heap.push({0, Start}), dist[Start] = 0;

	while (Heap.size())
	{
		auto Tmp = Heap.top();
		Heap.pop();

		int u = Tmp.second;
		if (Vis[u]) continue;
		Vis[u] = 1;

		for (int i = h[u]; ~i; i = ne[i])
		{
			int j = e[i];
			if (dist[j] > dist[u] + w[i])
			{
				dist[j] = dist[u] + w[i];
				Heap.push({dist[j], j});
			}
		}
	}
}

void Topsort()
{
	hh = 0, tt = -1;
	for (int i = 1; i <= N; i ++)
		if (!in[i])
			q[ ++ tt] = i;
	while (hh <= tt)
	{
		int u = q[hh ++];

		for (int i = hs[u]; ~i; i = ne[i])
		{
			int j = e[i];
			if ((-- in[j]) == 0)
				q[ ++ tt] = j;
		}
	}
}

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	memset(h, -1, sizeof h);
	memset(hs, -1, sizeof hs);

	cin >> N >> M >> X1 >> Y1 >> X2 >> Y2;

	int u, v, c;
	while (M --)
	{
		cin >> u >> v >> c;
		add(h, u, v, c), add(h, v, u, c);
	}

	Dijkstra(X1, D[0]), Dijkstra(Y1, D[1]);
	Dijkstra(X2, D[2]), Dijkstra(Y2, D[3]);

	for (int i = 1; i <= N; i ++)
		for (int j = h[i]; ~j; j = ne[j])
		{
			int k = e[j];
			if (D[0][i] + w[j] + D[1][k] == D[0][Y1] && D[2][i] + w[j] + D[3][k] == D[2][Y2])
				add(hs, i, k, w[j]), in[k] ++;
		}

	Topsort();

	for (int it = 0; it <= tt; it ++)
	{
		int i = q[it];
		for (int j = hs[i]; ~j; j = ne[j])
		{
			int k = e[j];
			F[k] = max(F[k], F[i] + w[j]);
		}
	}

	int Result = 0;
	for (int i = 1; i <= N; i ++)
		Result = max(Result, F[i]);

	memset(hs, -1, sizeof hs);
	memset(F, 0, sizeof F);
	memset(in, 0, sizeof in);

	for (int i = 1; i <= N; i ++)
		for (int j = h[i]; ~j; j = ne[j])
		{
			int k = e[j];
			if (D[0][i] + w[j] + D[1][k] == D[0][Y1] && D[3][i] + w[j] + D[2][k] == D[2][Y2])
				add(hs, i, k, w[j]), in[k] ++;//, cout << i << " " << k << endl;
		}

	Topsort();

	for (int it = 0; it <= tt; it ++)
	{
		int i = q[it];
		for (int j = hs[i]; ~j; j = ne[j])
		{
			int k = e[j];
			F[k] = max(F[k], F[i] + w[j]);
		}
	}

	for (int i = 1; i <= N; i ++)
		Result = max(Result, F[i]);

	cout << Result << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144