Cod sursa(job #1182874)
Utilizator | Vass Peter peti | Data | 7 mai 2014 22:23:55 |
---|---|---|---|
Problema | Floyd-Warshall/Roy-Floyd | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.67 kb |
#include <fstream>
#include <vector>
using namespace std;
int main(){
ifstream ifs("royfloyd.in");
ofstream ofs("royfloyd.out");
int N; ifs>>N;
vector<vector<int> > g(N,vector<int>(N,0));
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
ifs>>g[i][j];
for(int k=0;k<N;k++)
for(int i=0;i<N;i++)
for(int j=0;j<N;++j){
int t=g[i][k]+g[k][j];
if((g[i][j]>t || (g[i][j]==0 && i!=j)) && g[i][k] && g[k][j])
g[i][j]=t;
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++)
ofs<<g[i][j]<<" ";
ofs<<"\n";
}
}