2019-05-13 20:39:03 C++

C++

Copy Copied! Full
#include <bits/stdc++.h> using namespace std; #define INF 1e9+7 int main(void){ int N,M; cin >> N >> M; vector<vector<int>> d(N+1,vector<int>(N+1,INF)); for(int i=0;i<M;i++){ int u,v,l; cin >> u >> v >> l; d[u][v]=l; d[v][u]=l; } for(int i=1;i<=N;i++)d[i][i]=0; for(int i=1;i<=N;i++){ // 経由する頂点 for(int j=1;j<=N;j++){// 開始頂点 for(int k=1;k<=N;k++){// 終端 printf("経由する頂点:%d 開始頂点:=%d 終端:%d\n",i,j,k); printf("d[%d][%d]=min(d[%d][%d],d[%d][%d]+d[%d][%d]);\n" ,j,k,j,k,j,i,i,k); printf("d[%d][%d]=min(%d,%d+%d) = %d \n" ,j,k,d[j][k],d[j][i],d[i][k],min(d[j][k],d[j][i]+d[i][k])); d[j][k]=min(d[j][k],d[j][i]+d[i][k]); } } } cout << d[1][3] << endl; }
RECOMMEND