Link
很经典的图论题目，分析下来不是特别有难度，算是比较简单的一类拓扑题吧。
首先对于题目给定的$S1,S2,T1,T2$肯定要分别求一遍最短路，而我们选择的是从这四个节点出发分别求对所有点的最短路，得到$Dist[1 -> 4][i]$分别表示$S1,T1,S2,T2$出发到第$i$个节点的最短路。
因为题目是无向图，所以考虑重新建图变成$DAG$。
在这之前我们要知道一个结论，就是这个最长公共路经一定是一条链，具体很好推，瞎证一证就可以了。
所以如果我们在这里有了一张关于$S1 -> T2$的所有最短路组成的$DAG$，那么其最长公共路经一定在这个图上，反过来$S2->T2$也是成立的。
所有我们取一个交集，就知道怎么建图了：
1.首先大循环是建一个$S1->T1$的图，对于某一条边$(Now->To)$，我们只需要判断$S1->Now->To->T1$这条路经是不是$S1->T1$的最短路就可以了。
于是
1 | if (Dist[1][E[i].F] + E[i].L + Dist[2][E[i].T] == Dist[1][T1]) |
2.之后循环的是$S2->T2$，和上面一样，但是为了保证$S2->Now->T->T2$和$S2->T->Now->T2$这两种情况都可以考虑到，我们需要分别考虑。1
2
3
4
5
6
7
8for (int i = 1 ; i <= Tot ; i ++)
if (Dist[1][E[i].F] + E[i].L + Dist[2][E[i].T] == Dist[1][T1]) {
if (Dist[3][E[i].F] + E[i].L + Dist[4][E[i].T] == Dist[3][T2])
Add2(E[i].F, E[i].T, E[i].L, 1) ;
else if (Dist[3][E[i].T] + E[i].L + Dist[4][E[i].F] == Dist[3][T2])
Add2(E[i].F, E[i].T, E[i].L, 1) ;
else Add2(E[i].F, E[i].T, E[i].L, 0) ;
}
看到这个建新图的函数$Add2()$中最后有一个关于$1$和$0$的参数，这个是为了表达在拓扑排序中是否需要计入答案的,也就是说这条边是不是在两条最短路的交集上（好绕~。
然后就是一个拓扑排序了，直接从$S1$跑到$T1$，然后在其中对答案取$max$就可以了。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
using namespace std ;
typedef long long LL ;
const int MAXN = 800010 ;
const int MAXM = 800010 ;
const int Inf = 0x7fffffff ;
int N, M, D[MAXN], H[MAXN], Tot, Ans[MAXN] ;
int S1, S2, T1, T2, Dist[6][MAXN], Ind[MAXN] ;
struct EDGE{
int F ; int T ; int Next ; int L ;
} E[MAXM << 1] ;
int H2[MAXN], Tot2 ;
struct EDGE2 {
int F ; int T ; int Next ; int L ;
bool P ;
} Ed[MAXM << 1] ;
struct NODE {
int Num ; long long Len ;
bool operator < (const NODE & B) const {
return Len > B.Len ;
}
} Node ;
bool Vis[MAXN] ;
priority_queue<NODE> Q ;
inline int Read() {
int X = 0, F = 1 ; char ch = getchar() ;
while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
return X * F ;
}
inline void Add(int F, int T, int L) {
E[++ Tot].F = F, E[Tot].T = T, E[Tot].L = L ;
E[Tot].Next = H[F], H[F] = Tot ;
}
inline void Add2(int F, int T, int L, int P) {
Ed[++ Tot2].F = F, Ed[Tot2].T = T, Ed[Tot2].L = L ;
Ed[Tot2].Next = H2[F], H2[F] = Tot2, Ed[Tot2].P = P ;
}
inline void Dijkstra(int S, int Num) {
memset(D, 127, sizeof(D)) ;
memset(Vis, 0, sizeof(Vis)) ;
while (! Q.empty()) Q.pop() ;
D[S] = 0 ; Vis[S] = 0 ; Node.Num = S ;
Node.Len = 0 ; Q.push(Node) ;
while (! Q.empty()) {
NODE Now = Q.top() ; Q.pop() ;
if (Vis[Now.Num]) continue ;
for (int i = H[Now.Num] ; i ; i = E[i].Next)
if (! Vis[E[i].T])
if (D[E[i].T] > D[Now.Num] + E[i].L) {
D[E[i].T] = D[Now.Num] + E[i].L ;
Q.push(Node = {E[i].T, D[E[i].T]}) ;
}
}
for (int i = 1 ; i <= N ; i ++)
Dist[Num][i] = D[i] ;
}
queue<int> Que ;
inline void Topo() {
Que.push(S1) ;
while (! Que.empty()) {
int Now = Que.front() ; Que.pop() ;
for (int i = H2[Now] ; i ; i = Ed[i].Next) {
Ind[Ed[i].T] -- ;
if (! Ind[Ed[i].T]) Que.push(Ed[i].T) ;
Ans[Ed[i].T] = max(Ans[Ed[i].T], Ans[Now] + Ed[i].L * Ed[i].P) ;
}
}
}
int main() {
N = Read(), M = Read() ;
S1 = Read(), T1 = Read(), S2 = Read(), T2 = Read() ;
for (int i = 1 ; i <= M ; i ++) {
int F = Read(), T = Read(), L = Read() ;
Add(F, T, L) ; Add(T, F, L) ;
}
Dijkstra(S1, 1) ; Dijkstra(S2, 3) ;
Dijkstra(T1, 2) ; Dijkstra(T2, 4) ;
for (int i = 1 ; i <= Tot ; i ++)
if (Dist[1][E[i].F] + E[i].L + Dist[2][E[i].T] == Dist[1][T1]) {
if (Dist[3][E[i].F] + E[i].L + Dist[4][E[i].T] == Dist[3][T2])
Add2(E[i].F, E[i].T, E[i].L, 1) ;
else if (Dist[3][E[i].T] + E[i].L + Dist[4][E[i].F] == Dist[3][T2])
Add2(E[i].F, E[i].T, E[i].L, 1) ;
else Add2(E[i].F, E[i].T, E[i].L, 0) ;
Ind[E[i].T] ++ ;
}
Topo() ;
printf("%d\n", Ans[T1]) ;
return 0 ;
}