結果
問題 | No.1344 Typical Shortest Path Sum |
ユーザー |
![]() |
提出日時 | 2021-01-16 13:13:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 653 bytes |
コンパイル時間 | 1,835 ms |
コンパイル使用メモリ | 197,184 KB |
最終ジャッジ日時 | 2025-01-17 21:45:43 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 77 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf 1000000000000000000int main(){int N,M;cin>>N>>M;vector d(N,vector<long long>(N,Inf));rep(i,M){int s,t;long long D;cin>>s>>t>>D;s--;t--;d[s][t] = min(d[s][t],D);}rep(i,N)d[i][i] = 0LL;rep(i,N){rep(j,N){rep(k,N){if(d[j][i]==Inf||d[i][k]==Inf)continue;d[j][k] = min(d[j][k],d[j][i]+d[i][k]);}}}rep(i,N){long long ans = 0LL;rep(j,N){if(d[i][j]==Inf)continue;if(i==j)continue;ans += d[i][j];}cout<<ans<<endl;}return 0;}