結果
問題 | No.1344 Typical Shortest Path Sum |
ユーザー |
👑 |
提出日時 | 2022-10-25 14:13:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 47 ms / 2,000 ms |
コード長 | 1,384 bytes |
コンパイル時間 | 849 ms |
コンパイル使用メモリ | 75,776 KB |
最終ジャッジ日時 | 2025-02-08 12:35:59 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 77 |
ソースコード
#include <iostream>#include <vector>using namespace std;class FloydWarshall {long long MAX;void run(){for(int k = 0; n > k; k++){for(int i = 0; n > i; i++){for(int j = 0; n > j; j++){if(dist[i][k] == MAX || dist[k][j] == MAX)continue;dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);}}}}public:int n;vector<vector<long long>> dist;//MAX以上なら辺はなしFloydWarshall(int n_,long long MAX = 2e18+1):n(n_),MAX(MAX),dist(n_,vector<long long>(n_,MAX)){for(int i = 0; n > i; i++){dist[i][i] = 0;}}//双方向void push(int s,int v,long long c){dist[s][v] = min(dist[s][v],c);dist[v][s] = min(dist[s][v],c);}void push_p(int s,int v,long long c){dist[s][v] = min(dist[s][v],c);}bool negative(){for(int i = 0; n > i; i++){if(dist[i][i] < 0)return true;}return false;}bool isInf(int s,int v){return dist[s][v] == MAX;}void build(){run();}};int main(){int n,m;cin>>n>>m;FloydWarshall A(n);for(int i = 0; m > i; i++){long long a,b,c;cin>>a>>b>>c;A.push_p(--a,--b,c);}A.build();for(int i = 0; n > i; i++){long long ans = 0;for(int j = 0; n > j; j++){if(i==j || A.isInf(i,j))continue;ans += A.dist[i][j];}cout << ans << endl;}}