제출 #851646

#제출 시각아이디문제언어결과실행 시간메모리
851646_Nhm207_Commuter Pass (JOI18_commuter_pass)C++14
0 / 100
214 ms51168 KiB
#include<bits/stdc++.h> using namespace std; #define RUN_FAST ios_base::sync_with_stdio(false);cin.tie(0) ;cout.tie(0); #define HEAP_MIN(x) priority_queue<x,vector<x>,greater<x>> #define HEAP_MAX(x) priority_queue<x> #define refo(i , a , b) for(int i = a ; i >= b ; i--) #define rep(i , a , b) for(int i = a ; i < b ; i++) #define fo(i , a , b) for(int i = a ; i <= b ; i++) #define fov(x , y) for(auto x : y) #define bpc(x) __builtin_popcount(x) #define ii pair<int,int> #define iii pair<int,ii> #define iv pair<ii,ii> #define ll long long #define int long long #define endl "\n" #define psb push_back #define psf push_front #define pof pop_front() #define pob pop_back() #define ins insert #define fi first #define se second #define fr front() #define bk back() #define sz() size() const int N = 1e6 + 5; const int K = 105; const int mod = 1e9 + 7; const ll inf = 1e18; const double esp = 1e-6; const bool MoreThanOneTest = 0; int query , gt[N] ; int dx[] = { 1 , -1 , 0 , 0 }; int dy[] = { 0 , 0 , -1 , 1 }; int bit(int i , int k){ return ( i >> k ) & 1; } int off(int i , int k){ return i ^ ( 1 << k ); } int Pow(int n , int k){ if(k == 0) return 1; int t = Pow(n , k / 2) % mod; if(k % 2) return t * t % mod * n % mod; else return t % mod * t % mod; } void TinhGiaiThua(){ gt[0] = 1; fo(i , 1 , N - 5) gt[i] = (gt[i - 1] % mod * i % mod )% mod; return ; } int C(int n , int k){ k = gt[k] % mod * gt[n - k] % mod % mod; n = gt[n] % mod; return n % mod * Pow(k , mod - 2) % mod; } // ( a % mod ) / ( b % mod ) = a % mod * b ^ ( mod - 2) % mod // a ^ b % mod = a % mod ^ (b % (mod - 1)) // author : Nhm207 // DECLARE //__________________________________________________________ int n , m , u , v , c , s , t , ds[N] , dt[N] , du[N] , dv[N]; vector<ii> g[N]; bool ok[N]; bool in_path[N]; HEAP_MIN(ii) heap; //__________________________________________________________ void PreBuild(){ cin >> n >> m; cin >> s >> t; cin >> u >> v; fo(i , 1 , m){ cin >> u >> v >> c; g[u] . psb({v , c}); g[v] . psb({u , c}); } return; } void dijks(int s){ fo(i , 1 , n) ds[i] = inf; ds[s] = 0; heap . push({0 , s}); while(heap . sz()){ ii cur = heap . top(); heap . pop(); int u = cur . se; fov(tmp , g[u]){ int c = tmp . se; int v = tmp . fi; if(ds[v] > ds[u] + c){ ds[v] = ds[u] + c; heap . push({ds[v] , v}); } } } } void dijkt(int t){ fo(i , 1 , n) dt[i] = inf; dt[t] = 0; heap . push({0 , t}); while(heap . sz()){ ii cur = heap . top(); heap . pop(); int u = cur . se; fov(tmp , g[u]){ int c = tmp . se; int v = tmp . fi; if(dt[v] > dt[u] + c){ dt[v] = dt[u] + c; heap . push({dt[v] , v}); } } } } void dijku(int u){ fo(i , 1 , n) du[i] = inf; du[u] = 0; heap . push({0 , u}); while(heap . sz()){ ii cur = heap . top(); heap . pop(); int u = cur . se; fov(tmp , g[u]){ int c = tmp . se; int v = tmp . fi; if(du[v] > du[u] + c){ du[v] = du[u] + c; heap . push({du[v] , v}); } } } } void dijkv(int v){ fo(i , 1 , n) dv[i] = inf; dv[v] = 0; heap . push({0 , v}); while(heap . sz()){ ii cur = heap . top(); heap . pop(); int u = cur . se; fov(tmp , g[u]){ int c = tmp . se; int v = tmp . fi; if(dv[v] > dv[u] + c){ dv[v] = dv[u] + c; heap . push({dv[v] , v}); } } } } void _Nhm207_(){ dijks(s); dijkt(t); dijku(u); dijkv(v); memset(in_path , false , sizeof(in_path)); fo(i , 1 , n) if(ds[i] + dt[i] == ds[t]) in_path[i] = true; int ans = inf; fo(i , 1 , n){ if(in_path[i]){ ans = min(ans , du[i] + dv[i]); } } cout << ans; return; } int32_t main() { RUN_FAST //freopen(" .inp","r",stdin); //freopen(" .out","w",stdout); PreBuild(); if( MoreThanOneTest ){ cin >> query; while( query-- ){ _Nhm207_(); } } else _Nhm207_(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...