# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1003005 | tamir1 | Commuter Pass (JOI18_commuter_pass) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>using namespace std; #define N 300005#define ll long long int#define sz(x) (int)x.size()#define ff first#define ss second ll T, n, m, s, t, u1, u2, dis[N], a[N], b[N], c[N]; vector <pair<int,int>> v[N]; map <pair<int,int>, bool> vis; void dfs(int x){ for(auto i : v[x]){ if(dis[x] == dis[i.ff] + i.ss){ vis[{x,i.ff}] = 1; vis[{i.ff,x}] = 1; dfs(i.ff); return; } }} int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> s >> t >> u1 >> u2; for(int i = 1; i <= m; i++){ cin >> a[i] >> b[i] >> c[i]; v[a[i]].push_back({b[i],c[i]}); v[b[i]].push_back({a[i],c[i]}); } for(int i = 1; i <= n; i++) dis[i] = 1e15; priority_queue <pair<ll,ll>> q; q.push({0,s}); dis[s] = 0; while(!q.empty()){ int x = q.top().ss; if(dis[x] != -q.top().ff){ q.pop(); continue; } q.pop(); for(auto i : v[x]){ if(dis[i.ff] > dis[x] + i.ss){ dis[i.ff] = dis[x] + i.ss; q.push({-dis[i.ff], i.ff}); } } } dfs(t); for(int i = 1; i <= n; i++) v[i].clear(); for(int i = 1; i <= m; i++){ if(vis[{a[i],b[i]}] == 0){ v[a[i]].push_back({b[i],c[i]}); v[b[i]].push_back({a[i],c[i]}); } else { v[a[i]].push_back({b[i],0}); v[b[i]].push_back({a[i],0}); } } for(int i = 1; i <= n; i++) dis[i] = 1e15; q.push({0,u1}); dis[u1] = 0; while(!q.empty()){ int x = q.top().ss; if(dis[x] != -q.top().ff){ q.pop(); continue; } q.pop(); for(auto i : v[x]){ if(dis[i.ff] > dis[x] + i.ss){ dis[i.ff] = dis[x] + i.ss; q.push({-dis[i.ff], i.ff}); } } } cout << dis[u2]; return 0;}