Pagini recente » Borderou de evaluare (job #1971732) | Borderou de evaluare (job #1286537) | Cod sursa (job #2908210)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define INF 100000
ifstream f("royfloyd.in");
ofstream g("royfloyd.out");
int n; // nr de noduri
vector<vector<int>>d; // matricea costului minim al unui drum de la i la j care are vf intermediare in {1, ..., k}
vector<vector<int>>p; // predecesorul unui nod j pe drumul minim curent gasit de la i la j care are vf intermediare {1, ..., k}
void floydWarshall(){
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(d[i][j] > d[i][k] + d[k][j]){
d[i][j] = d[i][k] + d[k][j];
p[i][j] = i;
}
}
int main()
{
f >> n;
d.resize(n + 1, vector<int>(n + 1, INF));
p.resize(n + 1, vector<int>(n + 1, 0));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
int cost;
f >> cost;
d[i][j] = cost;
p[i][j] = i;
}
}
for(int i = 1; i <= n; i++)
d[i][i] = p[i][i] = 0;
floydWarshall();
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++)
if(d[i][j] == INF)
g << 0 << " ";
else
g << d[i][j] << " ";
g << "\n";
}
return 0;
}