제출 #1102534

#제출 시각아이디문제언어결과실행 시간메모리
1102534adaawfTravelling Merchant (CCO21_day2problem1)C++17
25 / 25
115 ms18768 KiB
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; struct EDGE { int x, y, z, t; } e[200005]; bool cmp(EDGE aa, EDGE bb) { return aa.z < bb.z; } vector<int> gg[200005]; int d[200005], da[200005], f[200005]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; for (int i = 1; i <= m; i++) { int x, y, z, t; cin >> x >> y >> z >> t; d[x]++; e[i] = {x, y, z, t}; } sort(e + 1, e + m + 1, cmp); queue<int> q; for (int i = 1; i <= m; i++) { gg[e[i].y].push_back(i); } for (int i = 1; i <= n; i++) { if (d[i] == 0) q.push(i); f[i] = 2e9; } while (!q.empty()) { int p = q.front(); q.pop(); f[p] = -1; for (int w : gg[p]) { d[e[w].x]--; da[w] = 1; if (d[e[w].x] == 0) { q.push(e[w].x); } } } for (int i = m; i >= 1; i--) { if (da[i]) continue; f[e[i].x] = min(f[e[i].x], e[i].z); d[e[i].x]--; da[i] = 1; if (d[e[i].x] == 0) { queue<int> q; q.push(e[i].x); while (!q.empty()) { int p = q.front(); q.pop(); for (int w : gg[p]) { if (da[w] == 1) continue; f[e[w].x] = min(f[e[w].x], max(f[p] - e[w].t, e[w].z)); da[w] = 1; d[e[w].x]--; if (d[e[w].x] == 0) { q.push(e[w].x); } } } } } for (int i = 1; i <= n; i++) cout << f[i] << " "; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...