| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1085700 | thaibeo123 | Commuter Pass (JOI18_commuter_pass) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fi first
#define se second
const int N = 1e5 + 5;
int n, m, s, t, x, y;
ll dx[N], dy[N], ans, dp[N][2], ds[N];
vector<pair<int, int>> g[N];
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
void dijkstra1(int u, ll d[]) {
for (int i = 1; i <= n; ++i) d[i] = 1e18;
d[u] = 0;
pq.push({d[u], u});
while (!pq.empty()){
int u = pq.top().se;
ll cost = pq.top().fi;
pq.pop();
if (cost > d[u]) continue;
for (pair<int, int> b : g[u]) {
int v = b.fi;
ll w = b.se;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
pq.push({d[v], v});
}
}
}
}
void dijkstra2(int x) {
for (int i = 1; i <= n; ++i) {
dp[i][0] = dp[i][1] = 1e18;
ds[i] = 1e18;
}
ds[x] = 0;
dp[x][0] = dx[x];
dp[x][1] = dy[x];
pq.push({ds[x], x});
while (!pq.empty()) {
int u = pq.top().se;
ll cost = pq.top().fi;
pq.pop();
if (cost > ds[u]) continue;
for (pair<int, int> b : g[u]) {
int v = b.fi;
ll w = b.se;
if (ds[v] > ds[u] + w) {
ds[v] = ds[u] + w;
dp[v][0] = min(dx[v], dp[u][0]);
dp[v][1] = min(dy[v], dp[u][1]);
pq.push({ds[v], v});
}
else if (ds[v] == ds[u] + w) {
dp[v][0] = min(dp[v][0], dp[u][0]);
dp[v][1] = min(dp[v][1], dp[u][1]);
}
}
}
ans = min(ans, dp[t][0] + dp[t][1]);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> s >> t >> x >> y;
for (int i = 1; i <= m; ++i) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dijkstra1(x, dx);
dijkstra1(y, dy);
ans = dx[y];
dijkstra2(s);
cout << ans;
return 0;
}