From 5fa155a32a976b50102fa8a30f4389afd41b6855 Mon Sep 17 00:00:00 2001 From: Ta180m Date: Sun, 3 May 2020 17:30:25 -0500 Subject: Create timeline.cpp --- 2020/February/Gold/timeline.cpp | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+) create mode 100644 2020/February/Gold/timeline.cpp 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 +#define f first +#define s second +using namespace std; +typedef pair ii; + +int S[100001]; +vector 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, greater> 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'; +} -- cgit v1.2.3-70-g09d2