結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー |
![]() |
提出日時 | 2023-12-04 01:51:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 160 ms / 2,000 ms |
コード長 | 1,754 bytes |
コンパイル時間 | 1,125 ms |
コンパイル使用メモリ | 61,480 KB |
実行使用メモリ | 25,472 KB |
最終ジャッジ日時 | 2024-09-26 22:37:24 |
合計ジャッジ時間 | 3,086 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 |
ソースコード
/* -*- coding: utf-8 -*-** 2569.cc: No.2569 はじめてのおつかいHard - yukicoder*/#include<cstdio>#include<vector>#include<queue>#include<algorithm>#include<utility>using namespace std;/* constant */const int MAX_N = 200000;const long long LINF = 1LL << 62;/* typedef */typedef long long ll;typedef pair<int,int> pii;typedef pair<ll,int> pli;typedef vector<pii> vpii;/* global variables */vpii nbrs[MAX_N], rnbrs[MAX_N];ll ds1[MAX_N], ds2[MAX_N], rds1[MAX_N], rds2[MAX_N];/* subroutines */void dijkstra(int n, int st, ll ds[], vpii nbrs[]) {fill(ds, ds + n, LINF);ds[st] = 0;priority_queue<pli> q;q.push({0, st});while (! q.empty()) {auto ue = q.top(); q.pop();ll ud = -ue.first;int u = ue.second;if (ds[u] != ud) continue;for (auto &vw: nbrs[u]) {int v = vw.first;ll vd = ud + vw.second;if (ds[v] > vd) {ds[v] = vd;q.push({-vd, v});}}}}/* main */int main() {int n, m;scanf("%d%d", &n, &m);for (int i = 0; i < m; i++) {int u, v, w;scanf("%d%d%d", &u, &v, &w);u--, v--;nbrs[u].push_back(pii(v, w));rnbrs[v].push_back(pii(u, w));}dijkstra(n, n - 2, ds1, nbrs);dijkstra(n, n - 1, ds2, nbrs);dijkstra(n, n - 2, rds1, rnbrs);dijkstra(n, n - 1, rds2, rnbrs);ll d12 = ds1[n - 1], d21 = ds2[n - 2];for (int k = 0; k < n - 2; k++) {ll mind = LINF;ll dk1 = rds1[k], d2k = ds2[k];ll dk2 = rds2[k], d1k = ds1[k];if (dk1 < LINF && d12 < LINF && d2k < LINF)mind = min(mind, dk1 + d12 + d2k);if (dk2 < LINF && d21 < LINF && d1k < LINF)mind = min(mind, dk2 + d21 + d1k);printf("%lld\n", mind < LINF ? mind : -1LL);}return 0;}