제출 #847103

#제출 시각아이디문제언어결과실행 시간메모리
847103ZeroScarCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
514 ms43804 KiB
#include<bits/stdc++.h> using namespace std; //#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //using namespace __gnu_pbds; //using ordered_set = tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>; //using ordered_multiset = tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>; //#define fbo find_by_order // use pointer, returns kth element (0-based) //#define ook order_of_key // returns x ada di index berapa (0-based) #define pb push_back #define pob pop_back #define fi first #define se second #define ll long long #define ld long double #define lll __int128 #define tp top() #define fr front() #define sz size() #define rep(i,a,b) for(int i = a; i < b; ++i) #define mem(a, b) memset(a, (b), sizeof(a)) #define clr(a) memset(a, 0, sizeof(a)) #define sqr(x) ( (x) * (x) ) #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() template<typename T> using ve = vector<T>; using pii = pair<int,int>; using ppi = pair<pii,int>; using pip = pair<int,pii>; using ppp = pair<pii,pii>; void optIO(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } const int N = 100020; const ll INF = 1e18; using pll = pair<ll,ll>; using pli = pair<pll,int>; vector<pli> adj[N]; ll dist[N]; void dijkstra(int s, int t) { for(int i = 0; i < N; i++) dist[i] = INF; priority_queue<pll, vector<pll>, greater<pll>> pq; pq.push({0,s}); while(pq.sz) { ll d = pq.tp.fi; int x = pq.tp.se; pq.pop(); if (dist[x] <= d) continue; dist[x] = d; for(auto to : adj[x]) pq.push({d + to.fi.se, to.fi.fi}); } set<pll> ms; ms.insert({dist[t], t}); while(ms.sz) { auto it = *(ms.rbegin()); ms.erase(it); int cur = it.se; for(auto &to : adj[cur]) if (dist[to.fi.fi] + to.fi.se == dist[cur]) { to.se = 1; ms.insert({dist[to.fi.fi], to.fi.fi}); } } } ll dij(int s, int t) { bool vis[N][3] = {0}; priority_queue<pli, vector<pli>, greater<pli>> pq; pq.push({{0,s},0}); while(pq.sz) { ll d = pq.tp.fi.fi; ll x = pq.tp.fi.se; int st = pq.tp.se; pq.pop(); if (vis[x][st]) continue; vis[x][st] = 1; if (x == t) return d; for(auto &to : adj[x]) { if (st == 2) pq.push({{d + to.fi.se,to.fi.fi},2}); else if (st == 1) { if (to.se == 1 && dist[x] == dist[to.fi.fi] + to.fi.se) pq.push({{d,to.fi.fi},1}); else pq.push({{d + to.fi.se,to.fi.fi},2}); } else { if (to.se == 1 && dist[x] == dist[to.fi.fi] + to.fi.se) pq.push({{d,to.fi.fi},1}); pq.push({{d + to.fi.se,to.fi.fi},0}); } } } return 0; } void solve(){ int n,m; cin>>n>>m; int s,t; cin>>s>>t; int u,v; cin>>u>>v; while(m--){ int uu,vv,ww; cin>>uu>>vv>>ww; adj[uu].pb({{vv,ww}, 0}); adj[vv].pb({{uu,ww}, 0}); } dijkstra(s,t); cout<<min(dij(u,v), dij(v,u))<<"\n"; } int main() { optIO(); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int t=1; // cin>>t; while(t--){ solve(); } 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...