結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー |
|
提出日時 | 2023-12-02 16:17:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 577 ms / 2,000 ms |
コード長 | 3,250 bytes |
コンパイル時間 | 2,405 ms |
コンパイル使用メモリ | 208,932 KB |
最終ジャッジ日時 | 2025-02-18 05:19:45 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename T> using min_priority_queue = priority_queue<T,vector<T>,greater<T>>;template<typename T>void printv(vector<T> &v){bool b = false;for(auto i : v){if(b) cout << " ";else b = true;cout << i;}cout << endl;}template <typename T>bool chmin(T &a, const T& b) {if (a > b) {a = b; // aをbで更新return true;}return false;}template <typename T>bool chmax(T &a, const T& b) {if (a < b) {a = b; // aをbで更新return true;}return false;}void yn(bool b){if(b) cout << "Yes" << endl;else cout << "No" << endl;}bool debug;bool randomInput;void input(){if(debug && randomInput){}else{}return;}void calc(){int64_t INF = 1001002003004005006;int N, M;cin >> N >> M;vector<vector<pair<int64_t, int>>> G(N);vector<vector<pair<int64_t, int>>> Ginv(N);for(int i = 0; i < M; i++){int u, v;int64_t t;cin >> u >> v >> t;u--; v--;G[u].push_back({t, v});Ginv[v].push_back({t, u});}vector<vector<int64_t>> D(2, vector<int64_t>(N, INF));D[0][N-1] = 0;D[1][N-2] = 0;auto Dinv = D;{for(int i = 0; i < 2; i++){min_priority_queue<pair<int64_t,int>> q;q.push({int64_t(0), N-1-i});while(q.size()){auto[d, pos] = q.top();q.pop();if(d > D[i][pos]) continue;for(auto[e, j] : G[pos]){if(chmin(D[i][j], d+e)){q.push({D[i][j], j});}}}}}{for(int i = 0; i < 2; i++){min_priority_queue<pair<int64_t,int>> q;q.push({int64_t(0), N-1-i});while(q.size()){auto[d, pos] = q.top();q.pop();if(d > Dinv[i][pos]) continue;for(auto[e, j] : Ginv[pos]){if(chmin(Dinv[i][j], Dinv[i][pos]+e)){q.push({Dinv[i][j], j});}}}}}vector<int64_t> ans(N-2, INF);for(int i = 0; i < N-2; i++){chmin(ans[i], Dinv[1][i] + D[1][N-1] + D[0][i]);chmin(ans[i], Dinv[0][i] + D[0][N-2] + D[1][i]);if(ans[i] == INF) ans[i] = -1;}for(int64_t i : ans){cout << i << endl;}/*for(auto i : D){for(auto j : i){cout << j << " ";}cout << endl;}for(auto i : Dinv){for(auto j : i){cout << j << " ";}cout << endl;}*/return;}int64_t ansSimple;void calcSimple(){return;}void calc1(){int t; cin >> t;for(int i = 0; i < t; i++){input();calc();calcSimple();}}int main(){debug = 0;randomInput = 0;srand(time(NULL));cout << fixed << setprecision(12);if(debug){calc1();}else{input();calc();}return 0;}//