| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1067745 | dwuy | Commuter Pass (JOI18_commuter_pass) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> pii;
const int MX = 200005;
int n, m, S, T, U, V;
vector<pii> G[MX];
int dS[MX];
int dT[MX];
int dU[MX];
int dV[MX];
int f1[MX];
int f2[MX];
void dijkstra(int X, int *d){
for(int i=0; i<=n; i++) d[i] = 1e18;
d[X] = 0;
priority_queue<pii> Q;
Q.push({0, X});
while(Q.size()){
int du, u;
tie(du, u) = Q.top();
Q.pop();
du = -du;
if(du != d[u]) continue;
for(pii edge: G[u]){
int v, c;
tie(v, c) = edge;
if(d[v] > du + c){
d[v] = du + c;
Q.push({-d[v], v});
}
}
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
//freopen("xebuyt.inp","r",stdin);
//freopen("xebuyt.out","w",stdout);
cin >> n >> m;
cin >> S >> T;
cin >> U >> V;
for(int i=1; i<=m; i++){
int u, v, c;
cin >> u >> v >> c;
G[u].push_back({v, c});
G[v].push_back({u, c});
}
dijkstra(S, dS);
dijkstra(T, dT);
dijkstra(U, dU);
dijkstra(V, dV);
vector<int> vt(n);
for(int i=0; i<n; i++) vt[i] = i + 1;
sort(vt.begin(), vt.end(), [&](const int &a, const int &b) -> bool {return dS[a] > dS[b];});
memset(f1, 0x3f, sizeof f1);
memset(f2, 0x3f, sizeof f2);
f1[T] = dU[T];
f2[T] = dV[T];
int ans = 1e18;
for(int u: vt) if(dS[u] + dT[u] == dS[T]){
for(pii edge: G[u]){
int v, c;
tie(v, c) = edge;
if(dS[v] + dT[v] == dS[T] && dS[v] > dS[u]){
f1[u] = min(f1[v], dU[u]);
f2[u] = min(f2[v], dV[u]);
}
}
ans = min({ans, f1[u] + dV[u], f2[u] + dU[u]});
}
cout << ans;
return 0;
}