Submission #807474

#TimeUsernameProblemLanguageResultExecution timeMemory
807474amine_arouaCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
437 ms23644 KiB
#include <bits/stdc++.h> //#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") using namespace std; #define int long long #define vi vector<int> #define vl vector<long long> #define vii vector<pair<int,int>> #define vll vector<pair<long long,long long>> #define pb push_back #define ll long long #define ld long double #define nl '\n' #define boost ios::sync_with_stdio(false) #define mp make_pair #define se second #define fi first #define fore(i, y) for(int i = 0; i < y; i++) #define forr(i,x,y) for(int i = x;i<=y;i++) #define forn(i,y,x) for(int i = y; i >= x; i--) #define all(v) v.begin(),v.end() #define sz(v) v.size() #define clr(v,k) memset(v,k,sizeof(v)) #define rall(v) v.rbegin() , v.rend() #define pii pair<int,int> #define pll pair<ll , ll> const ll MOD = 1e9 + 7; const int INF = 1e18 + 1; const int inf = 1e9 + 1; ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (gcd) ll lcm(ll a , ll b) {return a * (b / gcd(a , b));} // least common multiple (lcm) // HERE IS THE SOLUTION const int N = 100000; vii adj[N]; vi dp(N , INF) , dp0(N , INF); int n , m , s , t , u , v; vi spS , spT , spV , spU; int dfs(int x) { int &ans = dp[x]; if(ans != INF) return ans; ans = spV[x]; for(auto [y,c] : adj[x]) { if(spS[x] + spT[y] + c== spS[t]) ans = min(ans , dfs(y)); } return ans; } int dfs0(int x) { int &ans = dp0[x]; if(ans != INF) return ans; ans = spV[x]; for(auto [y,c] : adj[x]) { if(spS[y] + spT[x] + c== spS[t]) ans = min(ans , dfs0(y)); } return ans; } vi dijkstra(int start) { vi dist(n , INF); priority_queue<pii> pq; pq.push({0 , start}); dist[start] = 0; vector<bool> vis(n , 0); while(!pq.empty()) { int cur = pq.top().se; pq.pop(); if(vis[cur]) continue; vis[cur] = 1; for(auto [x , c] : adj[cur]) { if(dist[x] > dist[cur] + c){ dist[x] = dist[cur] + c; pq.push({-dist[x] , x}); } } } return dist; } bool cmp(int &a , int &b) { return spS[a] < spS[b]; } signed main() { cin>>n>>m>>s>>t>>u>>v; u-- , v-- , t-- , s--; fore(i , m) { int a , b,c; cin>>a>>b>>c; a-- , b--; adj[a].pb({b , c}); adj[b].pb({a , c}); } spS = dijkstra(s) , spT = dijkstra(t) , spV = dijkstra(v) , spU = dijkstra(u); int ans = INF; vi vv; fore(i , n) { vv.pb(i); } // sort(all(vv) , cmp); for(auto x : vv) { if(spS[x]+spT[x] == spS[t]) ans = min(ans , min(dfs0(x) ,dfs(x)) + spU[x]); } cout<<min(ans , spU[v])<<nl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...