結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー |
|
提出日時 | 2023-12-02 19:33:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 209 ms / 2,000 ms |
コード長 | 1,325 bytes |
コンパイル時間 | 2,076 ms |
コンパイル使用メモリ | 208,816 KB |
最終ジャッジ日時 | 2025-02-18 06:14:57 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;int main(){ios::sync_with_stdio(false);cin.tie(0);int n, m, u, v, w;cin >> n >> m;vector<vector<pair<int,int>>> g(n), g2(n);for(int i = 0; i < m; i++){cin >> u >> v >> w;g[--u].emplace_back(--v, w);g2[v].emplace_back(u, w);}vector<vector<ll>> dp(4);auto dijkstra = [&](int fr, vector<vector<pair<int,int>>> &g){vector<ll> dist(n, 1ll << 60);priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;pq.emplace(0, fr);dist[fr] = 0;while(!pq.empty()){ll d;tie(d, v) = pq.top();pq.pop();if(d > dist[v]) continue;for(auto &&[u, w] : g[v]){if(d + w >= dist[u]) continue;dist[u] = d + w;pq.emplace(dist[u], u);}}return dist;};dp[0] = dijkstra(n - 2, g);dp[1] = dijkstra(n - 2, g2);dp[2] = dijkstra(n - 1, g);dp[3] = dijkstra(n - 1, g2);for(int i = 0; i + 2 < n; i++){ll ans = dp[1][i] + dp[0][n - 1] + dp[2][i];ans = min(ans, dp[3][i] + dp[2][n - 2] + dp[0][i]);if(ans >> 60) ans = -1;cout << ans << '\n';}}