結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー |
![]() |
提出日時 | 2023-12-06 01:34:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 624 ms / 2,000 ms |
コード長 | 1,204 bytes |
コンパイル時間 | 4,969 ms |
コンパイル使用メモリ | 259,200 KB |
最終ジャッジ日時 | 2025-02-18 08:12:13 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 |
ソースコード
#include <stdio.h>#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using namespace atcoder;using mint = modint998244353;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 2000000000000000001vector<long long> get(vector<vector<pair<int,int>>> E,int s){int N = E.size();vector<long long> d(N,Inf64);d[s] = 0;priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> Q;Q.emplace(0,s);while(Q.size()>0){long long D = Q.top().first;int u = Q.top().second;Q.pop();if(D!=d[u])continue;rep(i,E[u].size()){int v = E[u][i].first;long long DD = E[u][i].second + D;if(d[v]>DD){d[v] = DD;Q.emplace(DD,v);}}}return d;}int main(){int N,M;cin>>N>>M;vector<vector<pair<int,int>>> E(N),e(N);rep(i,M){int a,b,c;cin>>a>>b>>c;a--,b--;E[a].emplace_back(b,c);e[b].emplace_back(a,c);}auto d0 = get(E,N-2),d1 = get(E,N-1),d2 = get(e,N-2),d3 = get(e,N-1);rep(i,N-2){long long ans = Inf64;ans = min(ans,d2[i] + d0[N-1] + d1[i]);ans = min(ans,d3[i] + d1[N-2] + d0[i]);if(ans==Inf64)ans = -1;cout<<ans<<endl;}return 0;}