結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー |
|
提出日時 | 2023-12-03 06:32:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 215 ms / 2,000 ms |
コード長 | 1,971 bytes |
コンパイル時間 | 1,500 ms |
コンパイル使用メモリ | 135,804 KB |
最終ジャッジ日時 | 2025-02-18 06:39:01 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 |
ソースコード
#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <chrono>#include <cmath>#include <complex>#include <cstdint>#include <cstring>#include <ctime>#include <deque>#include <iomanip>#include <iostream>#include <iterator>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <stack>#include <unordered_map>#include <unordered_set>void solve() {int n, m;std::cin >> n >> m;std::vector<std::vector<std::pair<long long, int>>> g(n), rg(n);for (int i = 0; i < m; i++) {int u, v;long long w;std::cin >> u >> v >> w;u--, v--;g[u].emplace_back(w, v);rg[v].emplace_back(w, u);}using info = std::pair<long long, int>;auto cal = [&](std::vector<std::vector<std::pair<long long, int>>>& g,int start) {std::priority_queue<info, std::vector<info>, std::greater<info>> pq;std::vector<long long> dp(n, 1e16);pq.emplace(0, start);dp[start] = 0;while (!pq.empty()) {auto [d, u] = pq.top();pq.pop();if (dp[u] == d) {for (auto [w, v] : g[u]) {if (dp[v] > dp[u] + w) {dp[v] = dp[u] + w;pq.emplace(dp[v], v);}}}}return dp;};auto d1 = cal(rg, n - 1);auto d2 = cal(rg, n - 2);auto d3 = cal(g, n - 1);auto d4 = cal(g, n - 2);auto p = [&](std::vector<long long>& A) {for (auto& x : A) std::cout << x << ' ';std::cout << '\n';};for (int k = 0; k < n - 2; k++) {long long ans = 1e16;long long a = d1[k] + d3[n - 2] + d4[k]; // k-> n-1 -> n-2 -> klong long b = d2[k] + d4[n - 1] + d3[k]; // k-> n-2 -> n-1 -> k;ans = std::min({ans, a, b});if (ans >= 1e16) ans = -1;std::cout << ans << '\n';}}int main() {std::ios_base::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;// std::cin >> t;while (t--) {solve();}}