11404번 플로이드

정식 알고리즘 명칭 : 플로이드 와샬 알고리즘

제출하였는데 계속 100%에서 틀렸다고 나오길래

생각해보니, 조건을 생각 못 했었다.

60번 째 줄 코드

비용은 100,000하고 같거나 작은 수이다.

즉, 시작 도시에서 끝 도시로 갈 때에 비용이 100,000 초과가 된다면, 

갈 수 없는 경우이므로 0을 출력해야한다.

https://www.acmicpc.net/problem/11404

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
 
#define INF 987654321
 
int cityCount = 0, busCount = 0;
 
int from = 0, to = 0, weight = 0;
 
int MIN(int a, int b)
{
    if (a <= b) return a;
    else return b;
}
 
int map[101][101] = { 0, };
 
int main()
{
    scanf("%d", &cityCount);
    scanf("%d", &busCount);
 
    for (int i = 1; i <= cityCount; i++)
    {
        for (int j = 1; j <= cityCount; j++)
        {
            map[i][j] = (i == j) ? 0 : INF;
        }
    }
 
    for (int i = 1; i <= busCount; i++)
    {
        scanf("%d %d %d", &from, &to, &weight);
        
        map[from][to] = MIN(map[from][to], weight);
    }
 
    for (int k = 1; k <= cityCount; k++)
    {
        for (int i = 1; i <= cityCount; i++)
        {
            for (int j = 1; j <= cityCount; j++)
            {
                if (i == j) continue;
 
                if (map[i][j] > map[i][k] + map[k][j])
                {
                    map[i][j] = map[i][k] + map[k][j];
                }
            }
        }
    }
 
    for (int i = 1; i <= cityCount; i++)
    {
        for (int j = 1; j <= cityCount; j++)
        {
            if (map[i][j] > 100000) map[i][j] = 0;
 
            printf("%d ", map[i][j]);
        }
 
        printf("\n");
    }
 
    return 0;
}