結果
| 問題 | No.160 最短経路のうち辞書順最小 |
| コンテスト | |
| ユーザー |
 T1610
|
| 提出日時 | 2026-10-15 23:56:28 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 5 ms / 5,000 ms |
| + 468µs | |
| コード長 | 10,188 bytes |
| 記録 | |
| コンパイル時間 | 4,902 ms |
| コンパイル使用メモリ | 393,492 KB |
| 実行使用メモリ | 9,872 KB |
| 最終ジャッジ日時 | 2026-10-15 23:56:41 |
| 合計ジャッジ時間 | 7,054 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 26 |
コンパイルメッセージ
main.cpp: In member function 'std::vector<Graph::Edge2> GraphUD::getEdge2()':
main.cpp:164:42: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
164 | if (i < e.to) ret.push_back({i, e.to, e.weight});
| ^
main.cpp: In member function 'std::vector<Graph::Edge2> GraphD::getEdge2()':
main.cpp:221:59: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
221 | rep(i, n) for (auto&& e : es[i]) { ret.push_back({i, e.to, e.weight}); }
| ^
ソースコード
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
#define rep(i, n) REP(i, 0, n)
#define REP(i, s, e) for (ll i = (s); i < (ll)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for (ll i = (ll)(s - 1); i >= (ll)(e); i--)
#define all(r) r.begin(), r.end()
#define rall(r) r.rbegin(), r.rend()
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
template <typename T, typename U>
T chmax(T& a, const U& b) {
if (a >= b) return false;
a = b;
return true;
}
template <typename T, typename U>
T chmin(T& a, const U& b) {
if (a <= b) return false;
a = b;
return true;
}
void yes_no(bool f, string yes = "Yes", string no = "No") { cout << (f ? yes : no) << "\n"; }
// 有向、無向グラフ共通クラス(隣接リスト)
struct Graph {
int n;
using WEIGHT_TYPE = long long;
const WEIGHT_TYPE INF = 1e18;
struct Edge {
int to;
WEIGHT_TYPE weight;
};
struct Edge2 {
int from;
int to;
WEIGHT_TYPE weight;
};
vector<vector<Edge>> es;
Graph(int n) : n(n), es(n) {}
// dijkstra O(E log V)
vector<WEIGHT_TYPE> dijkstra(int s) {
vector<WEIGHT_TYPE> d(n, INF);
d[s] = 0;
using P = pair<WEIGHT_TYPE, int>;
priority_queue<P, vector<P>, greater<P>> q;
q.push({0LL, s});
while (!q.empty()) {
auto p = q.top();
q.pop();
int cur = p.second;
auto cost = p.first;
if (d[cur] < p.first) continue;
for (auto& e : es[cur]) {
int to = e.to;
auto dist = e.weight + cost;
if (dist < d[to]) {
d[to] = dist;
q.push({dist, to});
}
}
}
return d;
}
// dijkstra O(V^2)
vector<WEIGHT_TYPE> dijkstra2(int s) {
vector<WEIGHT_TYPE> d(n, INF);
d[s] = 0;
vector<int> used(n);
auto mat = getEdgeMat();
while (1) {
int cur = -1;
rep(i, n) {
if (used[i]) continue;
if (cur == -1 || d[i] < d[cur]) cur = i;
}
if (cur == -1) break;
used[cur] = 1;
rep(i, n) { chmin(d[i], d[cur] + mat[cur][i]); }
}
return d;
}
// warshall_floyd O(n^3)
vector<vector<WEIGHT_TYPE>> warshall_floyd() {
// vector<vector<WEIGHT_TYPE>> d(n, vector<WEIGHT_TYPE>(n, INF));
// rep(i, n) d[i][i] = 0LL;
// rep(i, n) for (auto && e : es[i]) {
// int j = e.to;
// chmin(d[i][j], e.weight);
// }
auto d = getEdgeMat();
rep(k, n) rep(i, n) rep(j, n) { chmin(d[i][j], d[i][k] + d[k][j]); }
return d;
}
// 頂点sから到達できるか
vector<bool> getVisitable(int s) {
vector<bool> ret(n);
queue<int> q;
q.push(s);
ret[s] = true;
while (!q.empty()) {
auto cur = q.front();
q.pop();
for (auto&& e : es[cur]) {
if (!ret[e.to]) {
ret[e.to] = true;
q.push(e.to);
}
}
}
return ret;
}
// 2部グラフ判定
bool isBipartile() {
vector<int> memo(n, -1);
rep(i, n) {
if (memo[i] != -1) continue;
queue<int> q;
q.push(i);
memo[i] = 0;
while (!q.empty()) {
auto v = q.front();
q.pop();
for (auto&& e : es[v]) {
auto u = e.to;
if (memo[u] == -1) {
memo[u] = !memo[v];
q.push(u);
} else if (memo[u] == memo[v]) {
return false;
}
}
}
}
return true;
}
vector<vector<WEIGHT_TYPE>> getEdgeMat() {
vector<vector<WEIGHT_TYPE>> mat(n, vector<WEIGHT_TYPE>(n, INF));
rep(i, n) mat[i][i] = 0;
rep(i, n) {
for (auto&& e : es[i]) chmin(mat[i][e.to], e.weight);
}
return mat;
}
};
// 無向グラフ
struct GraphUD : public Graph {
GraphUD(int n) : Graph(n) {}
void add_edge(int from, int to, WEIGHT_TYPE weight) {
es[from].push_back({to, weight});
es[to].push_back({from, weight});
}
vector<Edge2> getEdge2() {
vector<Edge2> ret;
rep(i, n) for (auto&& e : es[i]) {
if (i < e.to) ret.push_back({i, e.to, e.weight});
}
return ret;
}
// 橋の検出
// http://nupioca.hatenadiary.jp/entry/2013/11/03/200006
// Calculate bridges in a undirected graph.
// Assume graph is connected and has no parallel edges or self-loops.
vector<Edge2> getBridges() {
int V = n;
// res: bridges
vector<Edge2> res;
// assume at least the first vertex exists
vector<int> low(V, -1); // lowest reacheable index
vector<int> pre(V, -1); // pre-order index
int count = 0; // pre-order index counter
// v: current node
// from: parent node
function<int(int, int)> dfs = [&](int v, int from) {
pre[v] = count++;
low[v] = pre[v];
for (auto&& e : es[v]) {
int to = e.to;
if (pre[to] == -1) {
// destination has not been visited
// visit destination and update low[v]
low[v] = min(low[v], dfs(to, v));
if (low[to] == pre[to]) {
// edge is not contained in a closed path -> bridge
res.push_back({v, to, e.weight});
}
} else {
if (from == to) {
// ignore a path to parent
continue;
}
low[v] = min(low[v], low[to]);
}
}
return low[v];
};
dfs(0, -1); // start dfs from vertex 0
return res;
}
};
// 有向グラフ
struct GraphD : public Graph {
GraphD(int n) : Graph(n) {}
void add_edge(int from, int to, WEIGHT_TYPE weight) {
es[from].push_back({to, weight});
}
vector<Edge2> getEdge2() {
vector<Edge2> ret;
rep(i, n) for (auto&& e : es[i]) { ret.push_back({i, e.to, e.weight}); }
return ret;
}
GraphD getReverseGraph() {
GraphD g(n);
rep(i, n) for (auto&& e : es[i]) { g.add_edge(e.to, i, e.weight); }
return g;
}
vector<vector<int>> scc() {
vector<vector<int>> res;
vector<int> cmp(n);
vector<int> vs;
vector<vector<int>> r_es(n);
rep(i, n) for (auto&& e : es[i]) {
int j = e.to;
r_es[j].push_back(i);
}
vector<bool> used(n);
function<void(int)> dfs = [&](int v) {
used[v] = true;
for (auto&& e : es[v]) {
int to = e.to;
if (!used[to]) dfs(to);
}
vs.push_back(v);
};
function<void(int, int)> rdfs = [&](int v, int k) {
used[v] = true;
cmp[v] = k;
for (auto&& to : r_es[v]) {
if (!used[to]) rdfs(to, k);
}
};
fill(all(used), 0);
vs.clear();
for (int v = 0; v < n; v++) {
if (!used[v]) dfs(v);
}
fill(all(used), 0);
int k = 0;
for (int i = vs.size() - 1; i >= 0; i--) {
if (!used[vs[i]]) rdfs(vs[i], k++);
}
res.clear();
res.resize(k);
for (int i = 0; i < n; i++) {
res[cmp[i]].push_back(i);
}
return res;
}
// bellmanFord 負閉路があるなら, dist[s] = INF | O(VE)
vector<WEIGHT_TYPE> bellmanFord(int s) {
vector<WEIGHT_TYPE> dist(n, INF);
dist[s] = 0;
auto es = getEdge2();
rep(i, n) {
for (auto&& e : es) {
if (dist[e.to] > dist[e.from] + e.weight) {
dist[e.to] = dist[e.from] + e.weight;
if (i == n - 1) {
dist[s] = INF;
return dist;
}
}
}
}
return dist;
}
// bellmanFord s->tの経路上に負閉路があるなら, dist[s] = INF | O(VE)
vector<WEIGHT_TYPE> bellmanFord2(int s, int t) {
vector<WEIGHT_TYPE> dist(n, INF);
auto f1 = getVisitable(s);
auto f2 = getReverseGraph().getVisitable(t);
dist[s] = 0;
auto es = getEdge2();
rep(i, n) {
for (auto&& e : es) {
if (!(f1[e.from] && f2[e.to])) continue;
if (dist[e.to] > dist[e.from] + e.weight) {
dist[e.to] = dist[e.from] + e.weight;
if (i == n - 1) {
dist[s] = INF;
return dist;
}
}
}
}
return dist;
}
};
void solve() {
int n, m, s, t;
cin >> n >> m >> s >> t;
GraphUD g(n);
rep(i, m) {
int a, b, c;
cin >> a >> b >> c;
g.add_edge(a, b, c);
}
auto d = g.dijkstra(t);
auto es = g.es;
rep(i, n) sort(all(es[i]), [](Graph::Edge a, Graph::Edge b) {
if (a.to != b.to) return a.to < b.to;
else return a.weight < b.weight;
});
int cur = s;
vi ans(1, cur);
while (cur != t) {
for (auto&& [to, v] : es[cur]) {
if (d[cur] == d[to] + v) {
ans.emplace_back(to);
cur = to;
break;
}
}
}
rep(i, ans.size()) cout << ans[i] << (i + 1 == (int)ans.size() ? '\n' : ' ');
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int t = 1;
// multi-testcase
// cin >> t;
rep(ti, t) solve();
return 0;
}