글 읽기 - [c++] 웜홀 어디서 틀린걸까요?

gi5005 3년 전 0

플로이드-와샬 알고리즘을 써서 dst 간선들을 모두 최소값으로 갱신한뒤

for(int i=1;i<=N;i++) 돌면서 dst[i][i]가 음수인 경우가 있으면 YES 아니면 NO이런 식으로 구현했는데 어디서 틀린건지 모르겠습니다.

// 백준 1865번
#include <bits/stdc++.h>
#define MAX 550
#define INF 1987654321
using namespace std;
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); 
    int TC;
    cin >> TC;
    while(TC--)
    {
        int dst[MAX][MAX];
        int N,M,W;
        cin >> N >> M >> W;
        for(int i=0;i<=N;i++)
        {
            for(int j=0;j<=N;j++)
            {
                if(i==j){
                    dst[i][j] =0;
                    continue;
                }
                dst[i][j] = INF;
            }
        }
        for(int i=0;i<M;i++)
        {
            int S,E,T;
            cin >> S >> E >> T;
            dst[S][E] = T;
            dst[E][S] = T;
        }
        for(int i=0;i<W;i++)
        {
            int S,E,T;
            cin >> S >> E >> T;
            dst[S][E] = -T;
        }
        // 중간 노드
        for(int k=1;k<=N;k++)
        {
            // 시작 노드
            for(int i=1;i<=N;i++)
            {
                // 도착 노드
                for(int j=1;j<=N;j++)
                {
                    if(dst[i][j] > dst[i][k]+dst[k][j])
                    {
                        dst[i][j] = dst[i][k]+dst[k][j];
                    }
                }
            }
        }
        string Back = "NO\n";
        for(int i=1;i<=N;i++)
        {
            if(dst[i][i]<0)
            {
                Back = "YES\n";
                break;
            }
        }
        cout << Back;
    }

}

playsworld16 3년 전 2

32, 33, 39줄에 공통적인 오류가 있습니다.

같은 두 지점을 잇는 경로가 여러번 나올 경우, 걸리는 시간에 상관없이 마지막으로 들어온 값을 저장하게 됩니다.

예를 들어 1 2 2 와 1 2 100 이 들어오면 dst[1][2] = 100이 되겠죠.

INF의 값도 문제가 있습니다. 50줄에서 dst[i][k]와 dst[k][j]가 모두 INF라면, dst[i][k] + dst[k][j] = 1987654321 * 2가 되는데, 이 값은 int 범위를 벗어나게 되어 -319658654라는 엉뚱한 값이 됩니다.

만약 dist[i][j]가 이 값보다 크다면 이 값으로 바뀌게 되죠.

gi5005 3년 전 0

앗 출발이랑 도착이 같은간선이 또 들어올 수 있다는걸 생각하지 못했군요...! 정말 감사합니다...ㅠㅠ

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

문제

문제

출처

ICPC

[c++] 웜홀 어디서 틀린걸까요?

gi5005 3년 전 0

playsworld16 3년 전 2

gi5005 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말