| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 744419 | MODDI | Commuter Pass (JOI18_commuter_pass) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, m, s1, e1, s2, e2;
const ll inf = 1e18;
vector<pii> G[100100];
vl dijkstra(int start){
vl dist(n);
for(int i = 0; i < n; i++) dist[i] = inf;
priority_queue<pair<ll, int>> pq;
pq.push(mp(0, start));
dist[start] = 0;
while(!pq.empty()){
int at = pq.top().second;
pq.pop();
for(auto next : G[at]){
if(dist[next.first] > dist[at] + next.second){
dist[next.first] = dist[at] + next.second;
pq.push(mp(-dist[next.first], next.first));
}
}
}
return dist;
}
ll pair1[2][100100], pair2[2][100100];
pair<ll,ll> st[100100];
bool ok[100100];
pll comb(pll a, pll b) {
return {min(a.first,b.first),min(a.second,b.second)};
}
int main(){
cin>>n>>m>>s1>>e1>>s2>>e2;
for(int i = 0; i < m; i++){
ll a, b, c;
cin>>a>>b>>c;
a--; b--;
G[a].pb(mp(b,c));
G[b].pb(mp(a,c));
}
// assert(false);
vl arr = dijkstra(s1);
for(int i = 0; i < n; i++) pair1[0][i] = arr[i];
arr = dijkstra(e1);
for(int i = 0; i < n; i++) pair1[1][i] = arr[i];
arr = dijkstra(s2);
for(int i = 0; i < n; i++) pair2[0][i] = arr[i];
arr = dijkstra(e2);
for(int i = 0; i < n; i++) pair2[1][i] = arr[i];
// assert(false);
for(int i = 0; i < n; i++) st[i] = {inf, inf};
ll ans = pair2[0][e2];
vector<pll> v;
memset(ok, false, sizeof ok);
for(int i = 0; i < n; i++){
if(pair1[0][i] + pair1[1][i] == pair1[0][e1]){
ok[i] = true;
v.pb({pair2[0][i], i});
}
}
sort(v.begin(), v.end());
for(auto a : v){
for(auto t : G[a.second]){
if(ok[t.first]) st[a.second] = comb(st[a.second], st[t.first]);
ans = min(ans, min(st[a.second].first + pair2[1][a.second], st[a.second].second + pair2[0][a.second]));
st[a.second] = comb(st[a.second], {pair2[0][a.second], pair2[1][a.second]});
}
cout<<ans<<endl;
return 0;
}