Submission #541389

#TimeUsernameProblemLanguageResultExecution timeMemory
541389_karan_gandhiCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
107 ms262144 KiB
// subtask 2 #include <bits/stdc++.h> using namespace std; #define all(v) v.begin(), v.end() #define endl '\n' #define pl(var) " [" << #var << ": " << (var) << "] " #define ll long long ll int inf = 1e16; void solve() { int n, m; cin >> n >> m; int s, t; cin >> s >> t; int U, V; cin >> U >> V; s--; t--; U--; V--; vector<vector<pair<int, ll int>>> adj(n); vector<vector<ll int>> wt(n, vector<ll int>(n, inf)); for (int i = 0; i < m; i++) { int a, b; ll int c; cin >> a >> b >> c; a--; b--; wt[a][b] = c; wt[b][a] = c; adj[a].emplace_back(b, c); adj[b].emplace_back(a, c); } { vector<int> came_from(n, -1); vector<ll int> dist(n, inf); dist[s] = 0; priority_queue<pair<ll int, int>> pq; pq.emplace(0, s); while (pq.size() != 0) { int u = pq.top().second; ll int cur_dist = pq.top().first * -1; pq.pop(); if (dist[u] != cur_dist) continue; for (auto [v, cost] : adj[u]) { ll int new_dist = cur_dist + cost; if (new_dist < dist[v]) { dist[v] = new_dist; came_from[v] = u; pq.emplace(-new_dist, v); } } } // assert(came_from[t] != -1); // int node = t; // while (node != -1) { // int prev = came_from[node]; // if (prev == -1) break; // wt[prev][node] = 0; // wt[node][prev] = 0; // node = prev; // } // vector<vector<pair<int, ll int>>> new_adj(n); // for (int i = 0; i < n; i++) { // // new_adj[i].emplace_back(a) // for (auto [v, _] : adj[i]) { // new_adj[i].emplace_back(v, wt[i][v]); // } // } // adj = new_adj; } // now run a djkstra from U to V vector<ll int> dist(n, inf); dist[U] = 0; priority_queue<pair<ll int, int>> pq; pq.emplace(0, U); while (pq.size() != 0) { int u = pq.top().second; ll int cur_dist = pq.top().first * -1; pq.pop(); for (auto [v, cost] : adj[u]) { ll int new_dist = cur_dist + cost; if (new_dist < dist[v]) { dist[v] = new_dist; pq.emplace(-new_dist, v); } } } // assert(dist[V] < inf); cout << dist[V] << endl; } int main() { // freopen(".in", "r", stdin); // freopen(".out", "w", stdout); ios::sync_with_stdio(false); cin.tie(nullptr); int T = 1; // cin >> T; while (T--) 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...