| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 387084 | Kepha | Commuter Pass (JOI18_commuter_pass) | C++11 | 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.
// JOI 2017/2018 Commuter Pass
#include <bits/stdc++.h>
#define MX 100000
#define int long long
using namespace std;
int N, M, S, T, U, V;
vector<pair<int, int> > edges[MX + 1];
int distU[MX + 1], distV[MX + 1], distS[MX + 1];
int dpU[MX + 1], dpV[MX + 1];
bool visited[MX + 1];
void dij1(int src, int dist[]) {
memset(visited, 0, sizeof(visited));
fill(dist + 1, dist + 1 + N, 0x3f3f3f3f);
priority_queue<pair<int, int> > q;
dist[src] = 0;
q.push({0, src});
while (q.size()) {
int node = q.top().second;
q.pop();
if (visited[node]) continue;
visited[node] = true;
for (auto& i : edges[node]) {
if (dist[node] + i.second < dist[i.first]) {
dist[i.first] = dist[node] + i.second;
q.push({-dist[i.first], i.first});
}
}
}
}
int dij2(int src, int end) {
memset(dpU, 0x3f, sizeof(dpU));
memset(dpV, 0x3f, sizeof(dpV));
memset(distS, 0x3f, sizeof(distS));
memset(visited, 0, sizeof(visited));
// distance, node, parent
priority_queue<pair<int, pair<int, int> > > q;
q.push({0, {src, 0}});
distS[src] = 0;
while (q.size()) {
int dist = q.top().first;
int node = q.top().second.first, parent = q.top().second.second;
q.pop();
if (!visited[node]) {
visited[node] = true;
distS[node] = dist;
dpU[node] = min(dpU[parent], distU[node]);
dpV[node] = min(dpV[parent], distV[node]);
for (auto& i : edges[node])
q.push({dist - i.second, {i.first, node}});
}
else if (-dist == distS[node]) {
if (min(distU[node], dpU[parent]) + min(distV[node], dpV[parent])
< dpU[node] + dpV[node]) {
dpU[node] = min(distU[node], dpU[parent]);
dpV[node] = min(distV[node], dpV[parent]);
}
}
}
return dpU[end] + dpV[end];
}
signed main() {
// ifstream cin("tmp");
cin >> N >> M >> S >> T >> U >> V;
for (int i = 1; i <= M; i++) {
int a, b, c; cin >> a >> b >> c;
edges[a].push_back({b, c});
edges[b].push_back({a, c});
}
dij1(U, distU);
dij1(V, distV);
int ans = distU[V];
ans = min(ans, dij2(S, T));
ans = min(ans, dij2(T, S));
cout << ans << "\n";
return 0;
}
© 2013-2021 박수찬