結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー |
![]() |
提出日時 | 2024-09-22 23:46:42 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 705 ms / 2,000 ms |
コード長 | 2,567 bytes |
コンパイル時間 | 3,223 ms |
コンパイル使用メモリ | 264,708 KB |
実行使用メモリ | 53,008 KB |
最終ジャッジ日時 | 2024-09-22 23:46:52 |
合計ジャッジ時間 | 8,038 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <class T>struct Edge {int from, to;T cost;int idx;Edge() {}Edge(int to_) : to(to_) {}Edge(int to_, T cost_) : to(to_), cost(cost_) {}Edge(int from_, int to_, int idx_) : from(from_), to(to_), idx(idx_) {}Edge(int from_, int to_, T cost_, int idx_) : from(from_), to(to_), cost(cost_), idx(idx_) {}};template <class T> using Graph = vector<vector<Edge<T>>>;using graph = Graph<long long>;using edge = Edge<long long>;#define add emplace_backstruct Dijkstra {private:graph g;int n, s;vector<long long> d;vector<edge> prev;vector<bool> visit;priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;public:Dijkstra(graph g_, int s_) : g(g_), n(g.size()), s(s_), d(n, 1000000000000000000), prev(n), visit(n, false) {d[s] = 0LL;pq.emplace(d[s], s);while (!pq.empty()) {int v = pq.top().second;pq.pop();if (visit[v]) {continue;}visit[v] = true;for (auto e : g[v]) {int nv = e.to;long long nc = e.cost;if (d[nv] > d[v] + nc) {d[nv] = d[v] + nc;prev[nv] = e;pq.emplace(d[nv], nv);}}}}vector<long long> dists() {return d;}long long dist(int t) {return d[t];}vector<edge> route(int t) {if (s == t || d[t] == 1000000000000000000) {return {};}vector<edge> res;int cur = t;while (cur != s) {res.emplace_back(prev[cur]);cur = prev[cur].from;}reverse(res.begin(), res.end());return res;}};using lint = long long;int main() {int n, m;cin >> n >> m;graph g(n), gg(n);for (int i = 0; i < m; i++) {int u, v;lint t;cin >> u >> v >> t;u--;v--;g[u].add(v, t);gg[v].add(u, t);}auto a = Dijkstra(gg, n - 2).dists();auto b = Dijkstra(gg, n - 1).dists();auto c = Dijkstra(g, n - 2).dists();auto d = Dijkstra(g, n - 1).dists();for (int i = 0; i < n - 2; i++) {lint ans = 1e18;ans = min({ans, a[i] + c[n - 1] + d[i], b[i] + d[n - 2] + c[i]});cout << (ans == 1e18 ? -1 : ans) << endl;}}