글 읽기 - 플로이드 와셜 방식 질문드립니다.

themion 3년 전 0

게시판 질문을 읽어보니까 알고리즘 문제는 아닌 것 같은데, 대체 어디서 틀린 걸까요?

#include <algorithm>
#include <cstdio>

int n, m;
int graph[101][101];

int main()
{
    int a, b, ret = -1, num = 0x3f3f3f3f;
    scanf("%d %d", &n, &m);

    std::fill(&graph[0][0], &graph[100][100], 0x3f3f3f3f);

    for (int i = 0; i < m; i++)
    {
        scanf("%d %d", &a, &b);
        graph[a][b] = 1;
        graph[b][a] = 1;
    }

    for (int k = 1; k <= n; k++)        //k: 경유 노드
        for (int i = 1; i <= n; i++)    //i: 시작 노드
        {
            if (i == k) continue;
            for(int j = 1; j <= n; j++) //j: 도착 노드
            {
                if (i == j || j == k) continue;
                graph[i][k] = std::min(graph[i][k], 
                                       graph[i][j] + graph[j][k]);
                graph[k][i] = graph[i][k];
            }
        }

    for (int i = 1; i <= n; i++)
    {
        graph[i][0] = 0;
        for (int j = 1; j <= n; j++) 
        {
            if (i == j) continue;
            graph[i][0] += graph[i][j];
        }

        if (num > graph[i][0])
        {
            num = graph[i][0];
            ret = i;
        }
    }

    printf("%d\n", ret);

    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

플로이드 와셜 방식 질문드립니다.

themion 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말