結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー |
![]() |
提出日時 | 2023-12-02 17:04:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 327 ms / 2,000 ms |
コード長 | 1,526 bytes |
コンパイル時間 | 2,021 ms |
コンパイル使用メモリ | 205,348 KB |
最終ジャッジ日時 | 2025-02-18 05:52:39 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 |
ソースコード
#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define ALL(v) v.begin(), v.end()typedef long long ll;#include <bits/stdc++.h>using namespace std;const ll INF=1LL<<60;struct Edge{int to;ll w;Edge(int to,ll w) : to(to),w(w) {}};using Graph=vector<vector<Edge>>;using pli=pair<ll,int>;template<class T> bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}Graph G;vector<ll> dijkstra(int s){int n=G.size();vector<ll> dist(n,INF);dist[s]=0;priority_queue<pli,vector<pli>,greater<pli>> que;que.push({dist[s],s});while(!que.empty()){int v=que.top().second;ll d=que.top().first;que.pop();if(d>dist[v]) continue;for(auto e:G[v]){if(chmin(dist[e.to],dist[v]+e.w)){que.push({dist[e.to],e.to});}}}return dist;}int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);int n,m;cin>>n>>m;G.resize(n);vector<ll> A(m),B(m),T(m);rep(i,m){ll a,b,t;cin>>a>>b>>t;a--,b--;A[i]=a,B[i]=b,T[i]=t;;G[a].push_back(Edge(b,t));}vector<ll> dis1=dijkstra(n-2);vector<ll> dis2=dijkstra(n-1);G.resize(0);G.resize(n);rep(i,m){G[B[i]].push_back(Edge(A[i],T[i]));}vector<ll> dis3=dijkstra(n-2);vector<ll> dis4=dijkstra(n-1);rep(i,n-2){ll mi=INF;mi=min(mi,dis4[i]+dis2[n-2]+dis1[i]);mi=min(mi,dis3[i]+dis1[n-1]+dis2[i]);if(mi==INF) cout<<-1<<endl;else cout<<mi<<endl;}return 0;}