| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 833596 | vjudge1 | Commuter Pass (JOI18_commuter_pass) | C++17 | 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 ll long long
#define int long long
int n, m;
int s, t;
int u, v;
vector<vector<pair<int,int>>> edg;
bool vis[100005];
ll distS[100005];
ll distT[100005];
ll distU[100005];
ll distV[100005];
ll dist[305][305];
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
edg.resize(n+5);
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dist[i][j] = 1e18;
if (i == j) dist[i][j] = 0;
}
}
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
edg[a].push_back({b,c});
edg[b].push_back({a,c});
dist[a][b] = c;
dist[b][a] = c;
}
if (n <= 300) {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
ans = distU[v];
for (int i = 1; i <= n; i++) {
if (distS[i] + distT[i] != distS[t]) continue;
for (int j = 1; j <= n; j++) {
if (distS[j] + distT[j] != distS[t]) continue;
if (distS[i] + dist[i][j] + distT[j] == distS[t]
|| distS[j] + dist[j][i] + distT[i] == distS[t]
) {
ans = min(ans, distU[i] + distV[j]);
ans = min(ans, distV[i] + distU[j]);
}
}
}
cout << ans << '\n';
return 0;
}
priority_queue<pair<ll,int>> q;
q.push({0,s});
for (int i = 0; i <= n; i++) distS[i] = 1e18, vis[i] = 0;
distS[s] = 0;
while (!q.empty()) {
int f = q.top().second;
q.pop();
if (vis[f]) continue;
vis[f] = 1;
for (auto &[i,j] : edg[f]) {
if (!vis[i] && distS[i] > (ll) distS[f] + j) {
distS[i] = (ll) distS[f] + j;
q.push({-distS[i], i});
}
}
}
q.push({0,t});
for (int i = 0; i <= n; i++) distT[i] = 1e18, vis[i] = 0;
distT[t] = 0;
while (!q.empty()) {
int f = q.top().second;
q.pop();
if (vis[f]) continue;
vis[f] = 1;
for (auto &[i,j] : edg[f]) {
if (!vis[i] && distT[i] > (ll) distT[f] + j) {
distT[i] = (ll) distT[f] + j;
q.push({-distT[i], i});
}
}
}
q.push({0,u});
for (int i = 0; i <= n; i++) distU[i] = 1e18, vis[i] = 0;
distU[u] = 0;
while (!q.empty()) {
int f = q.top().second;
q.pop();
if (vis[f]) continue;
vis[f] = 1;
for (auto &[i,j] : edg[f]) {
if (!vis[i] && distU[i] > (ll) distU[f] + j) {
distU[i] = (ll) distU[f] + j;
q.push({-distU[i], i});
}
}
}
q.push({0,v});
for (int i = 0; i <= n; i++) distV[i] = 1e18, vis[i] = 0;
distV[v] = 0;
while (!q.empty()) {
int f = q.top().second;
q.pop();
if (vis[f]) continue;
vis[f] = 1;
for (auto &[i,j] : edg[f]) {
if (!vis[i] && distV[i] > (ll) distV[f] + j) {
distV[i] = (ll) distV[f] + j;
q.push({-distV[i], i});
}
}
}
ll ans = distU[v], Le = 1e18, Ri = 1e18;
for (int i = 1; i <= n; i++) {
if (distS[t] == distS[i] + distT[i]) {
Le = min(Le, distV[i]);
Ri = min(Ri, distU[i]);
}
}
ans = min(ans, Le + Ri);
cout << ans << '\n';
//cerr << "S: "; for (int i = 1; i <= n; i++) { cerr << distS[i] << " \n" [i == n]; }
//cerr << "T: "; for (int i = 1; i <= n; i++) { cerr << distT[i] << " \n" [i == n]; }
//cerr << "V: "; for (int i = 1; i <= n; i++) { cerr << distV[i] << " \n" [i == n]; }
return 0;
}