Submission #1243609

#TimeUsernameProblemLanguageResultExecution timeMemory
1243609longggggCrocodile's Underground City (IOI11_crocodile)C++17
89 / 100
2097 ms72116 KiB
#include <bits/stdc++.h> #define Longgggg ios_base::sync_with_stdio(0); cin.tie(0); #define ll long long using namespace std; #define fi first #define se second const ll LINF = 1e18; ll travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { vector<vector<pair<int,ll>>> adj(N); for (int i = 0; i < M; ++i) { adj[R[i][0]].push_back({R[i][1], L[i]}); adj[R[i][1]].push_back({R[i][0], L[i]}); } vector<ll> T(N, LINF); vector<bool> vis(N, false); // Ban đầu: tất cả exit T=0 using pli = pair<ll,int>; priority_queue<pli, vector<pli>, greater<pli>> pq; for (int i = 0; i < K; ++i) { T[P[i]] = 0; pq.push({0, P[i]}); } while (!pq.empty()) { auto [curT, u] = pq.top(); pq.pop(); if (vis[u]) continue; vis[u] = true; // Xét tất cả hàng xóm của u (node chưa xử lý) for (auto [v, w] : adj[u]) if (!vis[v]) { // Chuẩn bị xét update T[v] nếu đủ điều kiện // Tính giá trị tốt nhất và tốt nhì của T[x] + L(v,x) với x là hàng xóm v đã vào S vector<ll> vals; for (auto [x, wx] : adj[v]) if (vis[x]) { vals.push_back(T[x] + wx); } if (vals.size() < 2) continue; // Chưa thể xác định T[v] sort(vals.begin(), vals.end()); ll newT = vals[1]; // Tốt nhì! if (newT < T[v]) { T[v] = newT; pq.push({T[v], v}); } } } return T[0]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...