글 읽기 - 1504번 틀린 경우좀 찾아주세요

meme0724 9년 전 0

꼭 지나야 되는 특정한 지점을 m1, m2로 잡고 플로이드 알고리즘으로 각 지점간의 최단 거리를 모두 구한 뒤에

1->m1->m2->N 의 경로와 1->m2->m1->N중에서 더 짧은 거리를 해답으로 출력하는 방식이고

두 경로 모두다 거리가 210000000 이상이면 저 길이 없다는 뜻이니까 -1을 출력합니다.

어디에서 틀렸는지 좀 찾아주세요....

#include <stdio.h>
 
int mat[801][801] = { { 0, }, };
int min(int a, int b)
{
    if (a > b)
        return b;
    else
        return a;
}
int main()
{
    int i, j, n, e, a, b, c, m1, m2, k;
 
    scanf("%d %d", &n, &e);
    for (i = 0; i < 801; i++)
    {
        for (j = 0; j < 801; j++)
        {
            mat[i][j] = 210000000;
        }
    }
 
    for (i = 0; i < e; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        mat[a][b] = c;  mat[b][a] = c;
    }
    for (k = 1; k <= n; k++)
    {
        for (i = 1; i <= n; i++)
        {
            for (j = 1; j <= n; j++)
            {
                mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
            }
        }
    }
    scanf("%d %d", &m1, &m2);
    e = min(mat[1][m1] + mat[m1][m2] + mat[m2][n], mat[1][m2] + mat[m2][m1] + mat[m1][n]);
    if (e > 210000000)
        printf("-1");
    else
        printf("%d", e);
    return 0;
}

jng6017 9년 전 0

21억으로 초기화 시키셧는데 e가 21억보다 클때만 -1을 출력해서 그런게 아닐까 싶습니다.

21억 이상이면 부등호에 =이 추가 되어야할것같습니다.

algoshipda 9년 전 0

INF 너무 크게 잡아서 마지막 if문 위에서 min 계산할때 int 범위 넘을 수 있고 i==j 일때 mat[i][j] = 0으로 해줘야 하는듯 합니다.

algoshipda 9년 전 0

TLE 뜰거같은데 신기하게 안뜨네요

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

문제

문제

출처

ICPC

1504번 틀린 경우좀 찾아주세요

meme0724 9년 전 0

jng6017 9년 전 0

algoshipda 9년 전 0

algoshipda 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말