제출 #930314

#제출 시각아이디문제언어결과실행 시간메모리
930314LukapCommuter Pass (JOI18_commuter_pass)C++14
0 / 100
446 ms35068 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1e5 + 500; const ll INF = 1e16; int n, m; int s,t,u,v; vector<pair<int, ll> > susjedi[MAXN], parent[MAXN], dag[MAXN]; int bio[MAXN], bio2[MAXN]; queue<int> q; ll distu[MAXN], distv[MAXN], dists[MAXN]; pair<ll, ll> dp[MAXN]; ll rj = INF; set<pair<ll, ll> > sett; void bfs (int x) { for(int i = 0; i < n; i++){ if(i == s){ sett.insert(make_pair(0,s)); dists[s] = 0; continue; } sett.insert(make_pair(INF,i)); dists[i] = INF; } while(!sett.empty()){ int x = (*sett.begin()).second; sett.erase(sett.begin()); for (auto it: susjedi[x]) { int nx = it.first; if (dists[nx] > dists[x] + it.second) { sett.erase({dists[nx], nx}); dists[nx] = dists[x] + it.second; sett.insert ({dists[nx], nx}); parent[nx].clear (); parent[nx].push_back ({x, it.second}); } else if (dists[nx] == dists[x] + it.second) { parent[nx].push_back ({x, it.second}); } } } } void dfs (int x) { bio[x] = -2; for (auto nx: parent[x]) { dag[nx.first].push_back({x, nx.second}); if (bio[nx.first] != -2) dfs (nx.first); } } void dijkstra(){ for(int i = 0; i < n; i++){ if(i == u){ sett.insert(make_pair(0,u)); distu[u] = 0; continue; } sett.insert(make_pair(INF,i)); distu[i] = INF; } while(!sett.empty()){ int x = (*sett.begin()).second; sett.erase(sett.begin()); for (auto it: susjedi[x]) { int nx = it.first; if (distu[nx] > distu[x] + it.second) { sett.erase({distu[nx], nx}); distu[nx] = distu[x] + it.second; sett.insert ({distu[nx], nx}); } } } sett.clear (); for(int i = 0; i < n; i++){ if(i == v){ sett.insert(make_pair(0,v)); distv[v] = 0; continue; } sett.insert(make_pair(INF,i)); distv[i] = INF; } while(!sett.empty()){ int x = (*sett.begin()).second; sett.erase(sett.begin()); for (auto it: susjedi[x]) { int nx = it.first; if (distv[nx] > distv[x] + it.second) { sett.erase({distv[nx], nx}); distv[nx] = distv[x] + it.second; sett.insert ({distv[nx], nx}); } } } } void solve () { dijkstra (); for (int i = 0; i < n; i++) { if (bio[i] != -2) continue; dp[i].first = distu[i]; dp[i].second = distv[i]; } rj = distu[v]; memset (bio2, -1, sizeof (bio2)); q.push (s); bio2[s] = 0; return; while (!q.empty ()) { int x = q.front (); q.pop (); for (auto nx: dag[x]) { dp[nx.first].first = min (dp[nx.first].first, dp[x].first); // cout << "AAAAAA " << x << ' ' << nx.first << ' ' << dp[nx.first].first << ' ' << dp[nx.first].second << "\n"; if (bio2[nx.first] == -1) { bio2[nx.first] = bio[x] + 1; q.push (nx.first); } } } memset (bio2, -1, sizeof (bio2)); q.push (t); bio2[t] = 0; while (!q.empty ()) { int x = q.front (); q.pop (); for (auto nx: parent[x]) { dp[nx.first].second = min (dp[nx.first].second, dp[x].second); // cout << "AAAAAAAAAAAA" << ' ' << x << ' ' << dp[x].second << ' ' << nx.first << ' ' << dp[nx.first].second << "\n"; if (bio2[nx.first] == -1) { bio2[nx.first] = bio[x] + 1; q.push (nx.first); } } } for (int i = 0; i < n; i++) { if (bio[i] != -2) continue; rj = min (rj, dp[i].first + dp[i].second); dp[i].first = distu[i]; dp[i].second = distv[i]; } memset (bio2, -1, sizeof (bio2)); q.push (s); bio2[s] = 0; while (!q.empty ()) { int x = q.front (); q.pop (); for (auto nx: dag[x]) { dp[nx.first].second = min (dp[nx.first].second, dp[x].second); // cout << "AAAAAA " << x << ' ' << nx.first << ' ' << dp[nx.first].first << ' ' << dp[nx.first].second << "\n"; if (bio2[nx.first] == -1) { bio2[nx.first] = bio[x] + 1; q.push (nx.first); } } } memset (bio2, -1, sizeof (bio2)); q.push (t); bio2[t] = 0; while (!q.empty ()) { int x = q.front (); q.pop (); for (auto nx: parent[x]) { dp[nx.first].first = min (dp[nx.first].first, dp[x].first); // cout << "AAAAAAAAAAAA" << ' ' << x << ' ' << dp[x].second << ' ' << nx.first << ' ' << dp[nx.first].second << "\n"; if (bio2[nx.first] == -1) { bio2[nx.first] = bio[x] + 1; q.push (nx.first); } } } for (int i = 0; i < n; i++) { if (bio[i] != -2) continue; rj = min (rj, dp[i].first + dp[i].second); } } int main () { ios_base::sync_with_stdio (false); cin.tie (0); memset (bio, -1, sizeof (bio)); cin >> n >> m >> s >> t >> u >> v; s--;t--;u--;v--; for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; a--;b--; susjedi[a].push_back ({b, c}); susjedi[b].push_back ({a, c}); } bfs (s); dfs (t); solve (); cout << rj; 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...