Poloyd Algorithm
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
#include <stdio.h>
#include <stdlib.h>
#define MAX 101
#define INFI 9999999
int cityMap[MAX][MAX];
void initCityMap (int N) {
for (int s = 1; s <= N; s++) {
for (int v = 1; v <= N; v++) {
cityMap[s][v] = INFI;
}
}
}
void showCityMap (int N) {
for (int s = 1; s <= N; s++) {
for (int v = 1; v <= N; v++) {
if (cityMap[s][v] == INFI) {
printf("%d ", 0);
continue;
}
printf("%d ", cityMap[s][v]);
}
printf("\n");
}
}
void checkMoveCost (int N) {
for (int d = 1; d <= N; d++) {
for (int s = 1; s <= N; s++) {
if (s == d) {
continue;
}
for (int v = 1; v <= N; v++) {
if (s == v || s == d || v == d) {
continue;
}
if (cityMap[s][v] > cityMap[s][d] + cityMap[d][v]) {
cityMap[s][v] = cityMap[s][d] + cityMap[d][v];
}
}
}
}
}
int main(void) {
int N = 0;
int M = 0;
scanf("%d", &N);
scanf("%d", &M);
initCityMap(N);
for (int i = 0; i < M; i++) {
int s = 0;
int v = 0;
int w = 0;
scanf("%d %d %d", &s, &v, &w);
if (cityMap[s][v] > w) {
cityMap[s][v] = w;
}
}
checkMoveCost(N);
showCityMap(N);
return 0;
}
C
INFO