| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1318549 | peanut | Commuter Pass (JOI18_commuter_pass) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, m;
int S, T, U, V;
vector<pair<int, int>> adj[maxn];
vector<long long> dijkstra(int so) {
vector<long long> dist(n+1, LLONG_MAX);
dist[so] = 0;
priority_queue<pair<long long, int>> pq;
pq.push({0, so});
while (!pq.empty()) {
long long d = -pq.top().first;
int y = pq.top().second;
pq.pop();
if (d != dist[y]) continue;
for (auto x : adj[y]) {
if (d + x.second < dist[x.first]) {
dist[x.first] = d + x.second;
pq.push({-dist[x.first], x.first});
}
}
}
return dist;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
//freopen("PATH.INP", "r", stdin);
//freopen("PATH.OUT", "w", stdout);
cin >> n >> m >> S >> T >> U >> V;
for (int i = 1; i <= m; ++i) {
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<long long> distU = dijkstra(U);
vector<long long> distV = dijkstra(V);
vector<long long> dist(n+1, LLONG_MAX), mindistU(n+1, LLONG_MAX), mindistV(n+1, LLONG_MAX);
dist[S] = 0, mindistU[S] = distU[S], mindistV[S] = distV[S];
priority_queue<pair<long long, int>> pq;
pq.push({0, s});
while (!pq.empty()) {
long long d = -pq.top().first;
int y = pq.top().second;
pq.pop();
if (d != dist[y]) continue;
for (auto x : adj[y]) {
if (d + x.second < dist[x.first]) {
dist[x.first] = d + x.second;
mindistU[x.first] = min(mindistU[y], distU[x.first]);
mindistV[x.first] = min(mindistV[y], distV[x.first]);
pq.push({-dist[x.first], x.first});
}
else if (d + x.second == dist[x.first]) {
if (min(mindistU[y], distU[x.first]) + min(mindistV[y], distV[x.first]) < mindistU[x.first] + mindistV[x.first]) {
mindistU[x.first] = min(mindistU[y], distU[x.first]);
mindistV[x.first] = min(mindistV[y], distV[x.first]);
}
}
}
}
cout << min(distU[V], mindistU[T] + mindistV[T]);
return 0;
}