diff options
author | Ta180m | 2020-05-03 17:30:25 -0500 |
---|---|---|
committer | GitHub | 2020-05-03 17:30:25 -0500 |
commit | 5fa155a32a976b50102fa8a30f4389afd41b6855 (patch) | |
tree | 152057e2a68c649858f6fcc0f6cfc2db6aa4d8ad /2020/February/Gold/timeline.cpp | |
parent | d9371e95e2e3c5513b24ed7fdc5066eb7a3d364e (diff) |
Create timeline.cpp
Diffstat (limited to '2020/February/Gold/timeline.cpp')
-rw-r--r-- | 2020/February/Gold/timeline.cpp | 37 |
1 files changed, 37 insertions, 0 deletions
diff --git a/2020/February/Gold/timeline.cpp b/2020/February/Gold/timeline.cpp new file mode 100644 index 0000000..6a9c217 --- /dev/null +++ b/2020/February/Gold/timeline.cpp @@ -0,0 +1,37 @@ +#include <bits/stdc++.h> +#define f first +#define s second +using namespace std; +typedef pair<int, int> ii; + +int S[100001]; +vector<ii> G[100001]; + +int main() { + ifstream cin("timeline.in"); + ofstream cout("timeline.out"); + + int N, M, C; + cin >> N >> M >> C; + for (int i = 0; i < N; ++i) cin >> S[i]; + for (int i = 0; i < C; ++i) { + int a, b, x; + cin >> a >> b >> x; + G[--a].emplace_back(--b, -x); + } + for (int i = 0; i < N; ++i) S[i] = -S[i]; + priority_queue<ii, vector<ii>, greater<ii>> pq; + for (int i = 0; i < N; ++i) pq.emplace(S[i], i); + while (!pq.empty()) { + int d = pq.top().f, u = pq.top().s; + pq.pop(); + if (d > S[u]) continue; + for (auto& v : G[u]) { + if (S[u] + v.s < S[v.f]) { + S[v.f] = S[u] + v.s; + pq.emplace(S[v.f], v.f); + } + } + } + for (int i = 0; i < N; ++i) cout << -S[i] << '\n'; +} |