結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー |
![]() |
提出日時 | 2023-12-02 16:38:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 661 ms / 2,000 ms |
コード長 | 3,095 bytes |
コンパイル時間 | 4,502 ms |
コンパイル使用メモリ | 265,380 KB |
最終ジャッジ日時 | 2025-02-18 05:34:56 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/all>using namespace atcoder;#define rep(i, n) for(int i=0;i<(n);++i)#define rep1(i, n) for(int i=1;i<=(n);i++)#define ll long longusing mint = modint998244353;using P = pair<ll,ll>;using lb = long double;using T = tuple<ll, ll, ll>;#ifdef LOCAL# include <debug_print.hpp># define dbg(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)#else# define dbg(...) (static_cast<void>(0))#endifint main(){int n ,m;cin >> n >> m;vector<vector<P>> g(n), rev(n);rep(i,m){int a, b, c;cin >> a >> b >> c;--a;--b;g[a].emplace_back(b,c);rev[b].emplace_back(a,c);}priority_queue<T, vector<T>, greater<T>> pq;const ll INF = 1e18;vector<vector<ll>> dist1(n,vector<ll>(1<<2, INF));auto dist2 = dist1;auto revdist1 = dist1;auto revdist2 = dist1;dist1[n-1][2] = 0;dist2[n-2][1] = 0;pq.emplace(0,n-1,2);while(!pq.empty()){auto [d, u, s] = pq.top();pq.pop();if(d!=dist1[u][s]) continue;for(auto [v, c] : g[u]){int ns = s;if(v==n-1) ns |= 2;if(v==n-2) ns |= 1;if(dist1[v][ns]>dist1[u][s]+c){dist1[v][ns] = dist1[u][s] + c;pq.emplace(dist1[v][ns], v, ns);}}}pq.emplace(0, n-2, 1);while(!pq.empty()){auto [d, u, s] = pq.top();pq.pop();if(d!=dist2[u][s]) continue;for(auto [v, c] : g[u]){int ns = s;if(v==n-1) ns |= 2;if(v==n-2) ns |= 1;if(dist2[v][ns]>dist2[u][s]+c){dist2[v][ns] = dist2[u][s] + c;pq.emplace(dist2[v][ns], v, ns);}}}revdist1[n-1][2] = 0;revdist2[n-2][1] = 0;pq.emplace(0,n-1,2);while(!pq.empty()){auto [d, u, s] = pq.top();pq.pop();if(d!=revdist1[u][s]) continue;for(auto [v, c] : rev[u]){int ns = s;if(v==n-1) ns |= 2;if(v==n-2) ns |= 1;if(revdist1[v][ns]>revdist1[u][s]+c){revdist1[v][ns] = revdist1[u][s] + c;pq.emplace(revdist1[v][ns], v, ns);}}}pq.emplace(0, n-2, 1);while(!pq.empty()){auto [d, u, s] = pq.top();pq.pop();if(d!=revdist2[u][s]) continue;for(auto [v, c] : rev[u]){int ns = s;if(v==n-1) ns |= 2;if(v==n-2) ns |= 1;if(revdist2[v][ns]>revdist2[u][s]+c){revdist2[v][ns] = revdist2[u][s] + c;pq.emplace(revdist2[v][ns], v, ns);}}}dbg(dist1, dist2, revdist1, revdist2);rep(w,n-2){ll ans = INF;rep(i,1<<2)rep(j,1<<2){ll tmp = dist1[w][i] + revdist1[w][j];tmp = min(dist2[w][i] + revdist2[w][j],tmp);int ni = i|j;if(ni==3) ans = min(ans, tmp);}if(ans==INF) ans = -1;cout << ans << endl;}return 0;}