제출 #1088662

#제출 시각아이디문제언어결과실행 시간메모리
1088662MrPavlitoCommuter Pass (JOI18_commuter_pass)C++17
31 / 100
518 ms31476 KiB
#include <bits/stdc++.h> #define int long long #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define sc second #define endl "\n" #define pii pair<int,int> using namespace std; const int MAXN = 1e5+5; const int mod7 = 1e9+7; const long long inf = 1e18; int n,m; int a,b,c,d; set<pii> pq; vector<vector<int>> dist(4, vector<int>(MAXN, inf)); vector<vector<pii>> graf(MAXN); bool vis[MAXN]; int rez; vector<int> dist2(MAXN,inf); set<pii> smer; void diksta(int nod, int p) { dist[p][nod] = 0; pq.insert({dist[p][nod], nod}); while(!pq.empty()) { auto it = pq.begin(); int u = it->sc; pq.erase(it); for(auto x: graf[u]) { if(dist[p][x.fi] > dist[p][u] + x.sc) { pq.erase({dist[p][x.fi], x.fi}); dist[p][x.fi] = dist[p][u] + x.sc; pq.insert({dist[p][x.fi], x.fi}); } } } } void dikstra2(int nod) { fill(all(dist2), inf); dist2[nod] = 0; pq.insert({dist2[nod], nod}); while(!pq.empty()) { auto it = pq.begin(); int u = it->sc; pq.erase(it); for(auto x: graf[u]) { if(smer.count({u,x.fi})) { if(dist2[x.fi] > dist2[u]) { pq.erase({dist2[x.fi], x.fi}); dist2[x.fi] = dist2[u]; pq.insert({dist2[x.fi], x.fi}); } } else if(dist2[x.fi] > dist2[u] + x.sc) { pq.erase({dist2[x.fi], x.fi}); dist2[x.fi] = dist2[u] + x.sc; pq.insert({dist2[x.fi], x.fi}); } } } rez = min(rez, dist2[d]); } struct grana{int a,b,c;}; signed main() { ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0); int tt=1; //cin >> tt; while(tt--) { cin >> n >> m; cin >> a >> b >> c >> d; vector<grana> sve; for(int i=0; i<m; i++) { int u,v,w; cin >> u >> v >> w; sve.pb({u,v,w}); graf[u].pb({v,w}); graf[v].pb({u,w}); } diksta(a,0); diksta(b,1); diksta(c,2); rez = dist[2][d]; int distab = dist[0][b]; for(auto x: sve) { int u = x.a; int v = x.b; int w = x.c; if(dist[0][u] + dist[1][u] == distab && dist[0][v] + dist[1][v] == distab) { if(dist[0][u] < dist[0][v] && dist[0][u] + w == dist[0][v])smer.insert({u,v}); else if(dist[0][u] > dist[0][v] && dist[0][u] == w+ dist[0][v])smer.insert({v,u}); } } dikstra2(c); smer.clear(); for(auto x: sve) { int u = x.a; int v = x.b; int w = x.c; if(dist[0][u] + dist[1][u] == distab && dist[0][v] + dist[1][v] == distab) { if(dist[1][u] < dist[1][v] && dist[1][u] + w == dist[1][v])smer.insert({u,v}); else if(dist[1][u] > dist[1][v] && dist[1][u] == w+ dist[1][v])smer.insert({v,u}); } } dikstra2(c); cout << rez << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...