제출 #681207

#제출 시각아이디문제언어결과실행 시간메모리
681207Ninja_KunaiRelay Marathon (NOI20_relaymarathon)C++14
100 / 100
1884 ms97072 KiB
/** * Author : Nguyen Tuan Vu * Created : 12.01.2023 **/ #pragma GCC optimize("O2") #pragma GCC target("avx,avx2,fma") #include<bits/stdc++.h> #define MASK(x) ((1ll)<<(x)) #define BIT(x, i) (((x)>>(i))&(1)) #define ALL(v) (v).begin(), (v).end() #define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i) #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i) #define db(val) "["#val" = "<<(val)<<"] " #define TIME (1.0 * clock() / CLOCKS_PER_SEC) template <class X, class Y> bool minimize(X &a, Y b) { if (a > b) return a = b, true; return false; } template <class X, class Y> bool maximize(X &a, Y b) { if (a < b) return a = b, true; return false; } using namespace std; mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count()); int Rand(int l, int r) {return l + jdg() % (r - l + 1);} void file(){ #define TASK "TASK" if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); } } const int N = 1e5 + 5; const int INF = 1e9 + 7; int n, m, K, head[N], dist[N], MIN[2][4], dist2[N]; vector <pair <int, int>> adj[N]; vector <int> Spe, new_Spe; void dijkstra(vector <int> Spe) { FOR(i, 1, n) dist[i] = INF; priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> heap; for (auto x : Spe) { head[x] = x; heap.push({dist[x] = 0, x}); } while (heap.size()) { int du = heap.top().first; int u = heap.top().second; heap.pop(); if (du != dist[u]) continue; for (auto v : adj[u]) if (minimize(dist[v.second], dist[u] + v.first)) { heap.push({dist[v.second], v.second}); head[v.second] = head[u]; } } } int shortest_path(vector <int> Spe) { dijkstra(Spe); int D = INF; FOR(u, 1, n) for (auto x : adj[u]) { int v = x.second; if (head[v] != head[u]) { minimize(D, dist[v] + dist[u] + x.first); } } return D; } void dijkstra2(int x, int MIN[], int dist[]) { FOR(i, 1, n) dist[i] = INF; priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> heap; heap.push({dist[x] = 0, x}); while (heap.size()) { int du = heap.top().first; int u = heap.top().second; heap.pop(); if (du != dist[u]) continue; for (auto v : adj[u]) if (minimize(dist[v.second], dist[u] + v.first)) { heap.push({dist[v.second], v.second}); head[v.second] = head[u]; } } MIN[0] = MIN[1] = MIN[2] = INF; for (auto z : Spe) if (z != x) { if (dist[z] < MIN[0]) { MIN[3] = MIN[2]; MIN[2] = MIN[1]; MIN[1] = MIN[0]; MIN[0] = dist[z]; } else if (dist[z] < MIN[1]) { MIN[3] = MIN[2]; MIN[2] = MIN[1]; MIN[1] = dist[z]; } else if (dist[z] < MIN[2]) { MIN[3] = MIN[2]; MIN[2] = dist[z]; } else minimize(MIN[3], dist[z]); } } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); file(); cin >> n >> m >> K; FOR(i, 1, m) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({w, v}); adj[v].push_back({w, u}); } FOR(i, 1, K) { int x; cin >> x; Spe.push_back(x); } dijkstra(Spe); int A = 0, B = 0, D = INF; FOR(u, 1, n) for (auto x : adj[u]) { int v = x.second; if (head[v] != head[u] && minimize(D, dist[v] + dist[u] + x.first)) { A = head[u]; B = head[v]; } } //cout << A << ' ' << B << '\n'; for (auto x : Spe) if (x != A && x != B) new_Spe.push_back(x); int res = 2 * INF; minimize(res, shortest_path(Spe) + shortest_path(new_Spe)); dijkstra2(A, MIN[0], dist); dijkstra2(B, MIN[1], dist2); for (auto x : Spe) if (x != A && x != B) { int cost = dist2[x]; int bonus = 0; if (MIN[0][0] == dist[x] || MIN[0][0] == dist[A] || MIN[0][0] == dist[B]) { if (MIN[0][1] == dist[x] || MIN[0][1] == dist[A] || MIN[0][1] == dist[B]) { if (MIN[0][2] == dist[x] || MIN[0][2] == dist[A] || MIN[0][2] == dist[B]) { bonus = MIN[0][3]; } else bonus = MIN[0][2]; } else bonus = MIN[0][1]; } else bonus = MIN[0][0]; minimize(res, cost + bonus); } cout << res; cerr << "Time elapsed: " << TIME << " s.\n"; return 0; } /* ==================================================+ INPUT: | --------------------------------------------------| --------------------------------------------------| ==================================================+ OUTPUT: | --------------------------------------------------| --------------------------------------------------| ==================================================+ */

컴파일 시 표준 에러 (stderr) 메시지

RelayMarathon.cpp: In function 'void file()':
RelayMarathon.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...