제출 #948492

#제출 시각아이디문제언어결과실행 시간메모리
948492kornkinCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
247 ms20168 KiB
#include<bits/stdc++.h> using namespace std; #define pqpiig priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> #define ll long long ll n, m, s, t, u, v, dis[100001], par[100001]; vector<pair<ll, ll>> g[100001]; int main(){ ios_base::sync_with_stdio(0); cin >> n >> m >> s >> t >> u >> v; for(ll i = 0; i < m; i++){ ll u, v, w; cin >> u >> v >> w; g[u].push_back({v, w}); g[v].push_back({u, w}); par[i] = i; } memset(dis, 0x3f3f3f3f, sizeof(dis)); pqpiig pq; pq.push({0, s}); dis[s] = 0; while(!pq.empty()){ ll now = pq.top().second; pq.pop(); for(auto &[e, w] : g[now]){ if(dis[e] > dis[now] + w){ dis[e] = dis[now] + w; par[e] = now; pq.push({dis[e], e}); } } } for(ll i = par[t]; par[i] != i; i = par[i]) g[i].push_back({par[i], 0}), g[par[i]].push_back({i, 0}); memset(dis, 0x3f3f3f3f, sizeof(dis)); pq.push({0, u}); dis[u] = 0; while(!pq.empty()){ ll now = pq.top().second; pq.pop(); for(auto &[e, w] : g[now]){ if(dis[e] > dis[now] + w){ dis[e] = dis[now] + w; par[e] = now; pq.push({dis[e], e}); } } } //for(ll i = 1; i <= n; i++) cout << i << ": " << dis[i] << '\n'; cout << dis[v]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...