2019-05-30 14:20:48 C++

warshall_floyd

Copy Copied! Full
#include<bits/stdc++.h> using namespace std; //input //n m (vertex,edge) //a1 b1 c1 (from,to,cost) //...... //am bm cm //計算量O(N^3) //zero-origin #define rep(i,n) for(int i=0;i<(n);++i) template<class T>void chmin(T&a,T b){if(a>b)a=b;} typedef vector<vector<long>> graphs; const long MAX_N = 1000; const long INF = 1LL<<28; graphs d; int n,m; vector<long> a,b,c; void warshall_floyd(int n){ rep(i,n) //経由 rep(j,n) //開始 rep(k,n) //終点 chmin(d[j][k],d[j][i]+d[i][k]); } int main(){ cin>>n>>m; a=vector<long>(m); b=vector<long>(m); c=vector<long>(m); d=graphs(n,vector<long>(n,INF)); rep(i,m){ long A,B,C; cin>>A>>B>>C; A--;B--; //0-indexed d[A][B]=d[B][A]=C; } warshall_floyd(n); warshall_floyd(n); warshall_floyd(n); //念のため三回行う return 0; }
warshall_floyd
RECOMMEND