Submission #315001

#TimeUsernameProblemLanguageResultExecution timeMemory
315001aZvezdaCommuter Pass (JOI18_commuter_pass)C++14
0 / 100
606 ms30404 KiB
#include <bits/stdc++.h> using namespace std; //#pragma GCC optimize ("O3") //#pragma GCC target ("sse4") #define endl "\n" typedef long long ll; typedef long double ld; typedef unsigned long long ull; template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; } template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; } const ll mod = 1e12 + 7; template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}} #define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl const ll MAX_N = 1e5 + 10; ll helpDist[3][MAX_N]; vector<pair<ll, ll> > g[MAX_N]; ll dist[4 * MAX_N]; ll n, m; void helpDij(ll ind, ll start) { for(ll i = 0; i < MAX_N; i ++) { helpDist[ind][i] = mod; } helpDist[ind][start] = 0; priority_queue<pair<ll, ll> > pq; pq.push({0, start}); while(!pq.empty()) { auto curr = pq.top(); pq.pop(); curr.first *= -1; if(curr.first != helpDist[ind][curr.second]) {continue;} for(auto it : g[curr.second]) { if(helpDist[ind][it.first] > curr.first + it.second) { helpDist[ind][it.first] = curr.first + it.second; pq.push({-helpDist[ind][it.first], it.first}); } } } } ll dij(ll start, ll fin) { for(ll i = 0; i < MAX_N; i ++) { for(ll j = 0; j < 4; j ++) { dist[i + j * MAX_N] = mod; } } priority_queue<pair<ll, ll > > pq; dist[start] = 0; pq.push({0, start}); while(!pq.empty()) { auto curr = pq.top(); pq.pop(); curr.first *= -1; if(curr.first != dist[curr.second]) {continue;} ll x = curr.second % MAX_N, mask = curr.second / MAX_N; for(auto it : g[x]) { if(dist[it.first + mask * MAX_N] > curr.first && helpDist[2][it.first] >= helpDist[2][x]) { dist[it.first + mask * MAX_N] = curr.first; pq.push({-dist[it.first + mask * MAX_N], it.first + mask * MAX_N}); } } if(!(mask & 1)) { if(dist[curr.second + MAX_N] > curr.first + helpDist[0][x]) { dist[curr.second + MAX_N] = curr.first + helpDist[0][x]; pq.push({-dist[curr.second + MAX_N], curr.second + MAX_N}); } } if(!(mask & 2)) { if(dist[curr.second + 2 * MAX_N] > curr.first + helpDist[1][x]) { dist[curr.second + 2 * MAX_N] = curr.first + helpDist[1][x]; pq.push({-dist[curr.second + 2 * MAX_N], curr.second + 2 * MAX_N}); } } } return dist[fin + 3 * MAX_N]; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; ll s, t, u, v; cin >> s >> t >> u >> v; for(ll i = 0; i < m; i ++) { ll a, b, c; cin >> a >> b >> c; g[a].push_back({b, c}); g[b].push_back({a, c}); } helpDij(0, u); helpDij(1, v); helpDij(2, s); cout << min(dij(s, t), helpDist[0][v]) << endl; 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...