제출 #1019229

#제출 시각아이디문제언어결과실행 시간메모리
1019229KodikCommuter Pass (JOI18_commuter_pass)C++17
15 / 100
1314 ms262144 KiB
#include <bits/stdc++.h> using namespace std; #define ss second #define ff first typedef long long ll; #define int ll int mod = 1e9+7; // int inf = 1e18; signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); // ifstream cin ("shortcut.in"); // ofstream cout ("shortcut.out"); int n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v; --s; --t; --u; --v; unordered_map<int,int> adj[n]; for(int i = 0; i < m; ++i){ int a,b,c; cin >> a >> b >> c; --a; --b; if(!adj[a].count(b)) adj[a][b] = c; else adj[a][b] = min(adj[a][b], c); if(!adj[b].count(a)) adj[b][a] = c; else adj[a][b] = min(adj[b][a], c); } vector<int> dis(n, 1e18); dis[s] = 0; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; vector<int> par[n], chi[n]; pq.push({0, s}); while(!pq.empty()){ pair<int,int> a = pq.top(); pq.pop(); if(dis[a.ss]!=a.ff){ continue; } for(auto &[nxt, w] : adj[a.ss]){ if(a.ff+w<dis[nxt]){ par[nxt].clear(); par[nxt].push_back(a.ss); pq.push({a.ff+w, nxt}); dis[nxt] = a.ff+w; }else if(a.ff+w==dis[nxt]){ par[nxt].push_back(a.ss); } } } vector<bool> ways(n, false); queue<int> q; q.push({t}); while(!q.empty()){ int a = q.front(); q.pop(); ways[a] = true; for(int i : par[a]){ chi[i].push_back(a); q.push(i); } } vector<int> free[n]; for(int i = 0; i < n; ++i){ if(!ways[i]) continue; for(int j : par[i]){ if(ways[j]) free[i].push_back(j); } for(int j : chi[i]){ if(ways[j]) free[i].push_back(j); } } par->clear(); chi->clear(); using te = pair<int,pair<int,bool>>; priority_queue<te, vector<te>, greater<te>> ppq; ppq.push({0,{u,0}}); dis.assign(n, 1e18); dis[u] = 0; while(!ppq.empty()){ int weight = ppq.top().ff; int node = ppq.top().ss.ff; bool go = ppq.top().ss.ss; ppq.pop(); if(dis[node]!=weight){ continue; } if(ways[node]&&!go){ for(int &i : free[node]){ if(weight<dis[i]){ dis[i] = weight; ppq.push({weight,{i,i==s||i==t}}); } } } for(auto &[nxt, w] : adj[node]){ if(weight+w<dis[nxt]){ dis[nxt] = weight+w; ppq.push({weight+w,{nxt, go}}); } } } cout << dis[v] << '\n'; 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...