Submission #319649

#TimeUsernameProblemLanguageResultExecution timeMemory
319649GilgameshCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
366 ms23004 KiB
#include <bits/stdc++.h> //#include <bits/extc++.h> //#include <ext/pb_ds/assoc_container.hpp> // Common file //#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update using namespace std; //using namespace __gnu_pbds; //template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; using ull = unsigned ll; #define pb push_back #define mp make_pair #define eb emplace_back #define all(x) (x).begin(),(x).end() #define x first #define y second //const int MOD = 1e9 + 7; const int MOD = 998244353; const int dx[] = {0, 0, 1, -1}; const int dy[] = {1, -1, 0, 0}; const char dir[] = {'R', 'L', 'D', 'U'}; /* int add(int a, int b){ //(a + b) % 1e9 + 7 a += b; if(a < 0){ a += MOD; } if(a >= MOD){ a -= MOD; } return a; } int sub(int a, int b){ a -= b; if(a < 0) a += MOD; return a; } int mult(int a, int b){ return ((ll) a * b) % MOD; }*/ void setIO() { ios_base::sync_with_stdio(0); cin.tie(0); // freopen((s+".in").c_str(),"r",stdin); // freopen((s+".text").c_str(),"w",stdout); } const int mxN = 100'000; int n, m, s, t, u, v; vector<pii> adj[mxN]; ll du[mxN], dv[mxN], ds[mxN]; ll dp[2][mxN]; ll ans; void dijkstra(int src, ll dist[]){ for (int i = 0; i < n; ++i) dist[i] = LLONG_MAX; using T = pair<ll,int>; priority_queue<T,vector<T>,greater<T>> pq; dist[src] = 0; pq.push({0, src}); while (pq.size()) { ll cdist; int node; tie(cdist, node) = pq.top(); pq.pop(); if (cdist != dist[node]) continue; for (pair<int, int> i : adj[node]) { if (cdist+i.second < dist[i.first]) { pq.push({dist[i.first] = cdist+i.second, i.first}); } } } } ll solve(int start, int end){ bool visited[mxN]; fill(visited, visited + mxN, false); priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<pair<ll, pii>>> pq; pq.push(mp(0, mp(start, 0))); while (!pq.empty()) { auto cur = pq.top(); pq.pop(); ll c = cur.x; int node = cur.y.x; int par = cur.y.y; if (!visited[node]) { ds[node] = c; visited[node] = true; dp[0][node] = min(dp[0][par], du[node]); dp[1][node] = min(dp[1][par], dv[node]); for (auto& i : adj[node]) pq.push({c + i.y, mp(i.x, node)}); } else { if(c == ds[node] && min(du[node], dp[0][par]) + min(dv[node], dp[1][par]) <= dp[0][node] + dp[1][node]){ dp[0][node] = min(du[node], dp[0][par]); dp[1][node] = min(dv[node], dp[1][par]); } } } return dp[0][end] + dp[1][end]; } signed main(){ setIO(); //CHECK FOR LONG LONG!!! //LONG LONG OVERFLOW?? cin >> n >> m >> s >> t >> u >> v; --s; --t; --u; --v; for(int i = 0; i < m; ++i){ int a, b, c; cin >> a >> b >> c; --a; --b; adj[a].eb(mp(b, c)); adj[b].eb(mp(a, c)); } memset(dp, 0x3f, sizeof dp); dijkstra(u, du); dijkstra(v, dv); ans = min(du[v], solve(s, t)); cout << ans << "\n"; //CHECK FOR LONG LONG!!! }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...