結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー |
![]() |
提出日時 | 2016-07-01 16:06:39 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 23 ms / 5,000 ms |
コード長 | 1,777 bytes |
コンパイル時間 | 553 ms |
コンパイル使用メモリ | 61,528 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-12 00:01:54 |
合計ジャッジ時間 | 1,777 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <iostream> #include <vector> using namespace std; const int kINF = 1 << 28; const int kMAX_N = 210; const int kMAX_M = kMAX_N * (kMAX_N - 1) / 2; int N, M, S, G; int cost[kMAX_N][kMAX_N]; int next_node[kMAX_N][kMAX_N]; int a[kMAX_M], b[kMAX_M], c[kMAX_M]; void WarshallFloyd() { for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (cost[i][j] > cost[i][k] + cost[k][j]) { cost[i][j] = cost[i][k] + cost[k][j]; next_node[i][j] = next_node[i][k]; } else if (cost[i][j] == cost[i][k] + cost[k][j] && next_node[i][j] > next_node[i][k]) { next_node[i][j] = next_node[i][k]; } } } } } vector<int> RestoreRoute(int node, int goal) { vector<int> route; route.push_back(node); do { node = next_node[node][goal]; route.push_back(node); } while (node != goal); return route; } void Solve() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (i == j) { cost[i][j] = 0; next_node[i][j] = kINF; } else { cost[i][j] = kINF; next_node[i][j] = j; } } } for (int i = 0; i < M; i++) { cost[a[i]][b[i]] = cost[b[i]][a[i]] = c[i]; } WarshallFloyd(); vector<int> route = RestoreRoute(S, G); for (int i = 0; i < route.size(); i++) { cout << (i == 0 ? "" : " ") << route[i] << (i == route.size() - 1 ? "\n" : ""); } } int main() { cin >> N >> M >> S >> G; for (int i = 0; i < M; i++) { cin >> a[i] >> b[i] >> c[i]; } Solve(); return 0; }