제출 #1043272

#제출 시각아이디문제언어결과실행 시간메모리
1043272MinbaevCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
116 ms27576 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast,unroll-loops") using namespace std; using namespace __gnu_pbds; #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define f first #define s second #define int long long #define pii pair<int,int> #define ar array template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;} template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;} typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const int inf = 1e17 + 7; const int mod = 1e9 + 7; const int N = 3e5 + 5; const int md = 998244353; int binpow(int a, int b){ if(b == 0)return 1; if(b % 2 == 0){ int c = binpow(a,b/2); return (c*c)%mod; } return (binpow(a,b-1)*a)%mod; } int divi(int a, int b){ return (a*(binpow(b,mod-2)))%mod; } int n,m,k; vector<pii>g[N]; void solve(){ cin >> n >> m; int a,b,c,d; cin >> a >> b >> c >> d; while(m--){ int l,r,x; cin >> l >> r >> x; g[l].pb({r,x}); g[r].pb({l,x}); } priority_queue<pii, vector<pii>,greater<pii>>q; vector<int>dp(n+1, inf), pr(N); dp[b] = 0; q.push({0, b}); while(!q.empty()){ auto x = q.top().s; auto cost = q.top().f; q.pop(); if(dp[x] < cost)continue; for(auto &[to,t]:g[x]){ if(umin(dp[to], cost + t)){ q.push({dp[to], to}); } } } vector<int>dp1(n+1, inf); dp1[a] = 0; q.push({0, a}); while(!q.empty()){ auto x = q.top().s; auto cost = q.top().f; q.pop(); if(dp1[x] < cost)continue; for(auto &[to,t]:g[x]){ if(umin(dp1[to], cost + ((dp[x] > dp[to]) ? 0 : t))){ q.push({dp1[to], to}); } } } cout << dp1[d] << "\n"; } /* */ signed main() { // freopen("seq.in", "r", stdin); // freopen("seq.out", "w", stdout); ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); int tt=1;//cin>>tt; while(tt--)solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...