結果

問題 No.2569 はじめてのおつかいHard
ユーザー Tatsu_mr
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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_back
struct 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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0