結果
問題 | No.1344 Typical Shortest Path Sum |
ユーザー |
![]() |
提出日時 | 2021-01-16 15:04:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 923 bytes |
コンパイル時間 | 2,454 ms |
コンパイル使用メモリ | 197,456 KB |
最終ジャッジ日時 | 2025-01-17 23:27:06 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 77 |
ソースコード
#include "bits/stdc++.h" using namespace std; using ll = long long; using P = pair<ll, ll>; const ll INF = (1LL << 61); ll mod = (ll)1e9 + 7; signed main() { ios::sync_with_stdio(false); cin.tie(0); ll N, M; cin >> N >> M; vector<vector<ll>>d(N, vector<ll>(N, INF)); for (int i = 0; i < N; i++) { d[i][i] = 0; } for (int i = 0; i < M; i++) { ll s, t, c; cin >> s >> t >> c; s--; t--; d[s][t] = min(d[s][t], c); } for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } for (int i = 0; i < N; i++) { ll ans = 0; for (int j = 0; j < N; j++) { if (d[i][j] >= INF / 3 || i == j)continue; ans += d[i][j]; } cout << ans << endl; } return 0; }