#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int maxn = 1e5 + 5;
int n, m, S, T, U, V;
vector<pii> graph[maxn+5];
vector<int> G[maxn+5];
vector<array<int, 3> > edges;
ll dist[3][maxn+5];
void D(int s, int t) {
priority_queue<pll, vector<pll>, greater<pll> > pq;
for(int i=1; i<=n; i++) dist[t][i] = 1e18;
dist[t][s] = 0; pq.push({ 0, s });
while(!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if(d != dist[t][u]) continue;
for(auto &[v, w] : graph[u]) {
if(dist[t][v] > d + w) {
dist[t][v] = d + w;
pq.push({ d + w, v });
}
}
}
}
int main() {
cin >> n >> m >> S >> T >> U >> V;
for(int i=0; i<m; i++) {
int a, b, w;
cin >> a >> b >> w;
edges.push_back({ a, b, w });
graph[a].push_back({ b, w });
graph[b].push_back({ a, w });
}
D(S, 0);
D(U, 1);
D(V, 2);
vector<int> in(n+1), topo; queue<int> q;
for(auto &[a, b, w] : edges) {
if(dist[0][a] + w == dist[0][b]) G[a].push_back(b), in[b]++;
if(dist[0][b] + w == dist[0][a]) G[b].push_back(a), in[a]++;
}
q.push(S);
while(!q.empty()) {
int u = q.front(); q.pop();
topo.push_back(u);
for(int &v : G[u]) if(--in[v] == 0) q.push(v);
}
vector<ll> dpU(n+1, 1e18), dpV(n+1, 1e18), dp(n+1, 1e18);
dpU[S] = dist[1][S]; dpV[S] = dist[2][S]; dp[S] = dpU[S] + dpV[S];
for(int &u : topo) {
dp[u] = min({ dp[u], dpU[u] + dist[2][u], dpV[u] + dist[1][u] });
for(int &v : G[u]) {
dp[v] = min(dp[v], dp[u]);
dpU[v] = min({ dpU[v], dpU[u], dist[1][v] });
dpV[v] = min({ dpV[v], dpV[u], dist[2][v] });
}
}
cout << min(dp[T], dist[1][V]) << '\n';
return 0;
}
Compilation message
/usr/bin/ld: /tmp/cc2dkuCf.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccAjSX7e.o:crocodile.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc2dkuCf.o: in function `main':
grader.cpp:(.text.startup+0x36): undefined reference to `travel_plan(int, int, int (*) [2], int*, int, int*)'
collect2: error: ld returned 1 exit status
