글 읽기 - 다익스트라로 정답처리 됩니다.(정답코드 주의)

seungwuk98 2년 전 0

다익스트라 안에서 50번 이상 재방문하고 0보다 작아지는 경우가 있으면 루프라고 판단하고 exit하는 코드라고 보면 될것 같습니다.

데이터가 약한걸까요? 아니면 이렇게 풀어도 되는건가요??

추) 플루이드 와샬로 아무리 줄여봐도 93퍼 이상으로 시간이 안되더군요. 플루이드 와샬로 푸는 것은 아예 불가능한 것일까요?

import sys
from heapq import *
input = sys.stdin.readline


def dijkstra(g, s):
    distance = [1e9]*(n+1)
    heap = [(0, s)]
    visit = [0]*(n+1)
    while heap:
        dist, node = heappop(heap)
        visit[node] += 1
        for next_dist, next_node in g[node]:
            from_start = next_dist+dist
            if visit[next_node] > 50 and from_start < 0:
                return 0
            if from_start < distance[next_node]:
                distance[next_node] = from_start
                heappush(heap, (from_start, next_node))

    return 1


for _ in range(int(input())):
    n, m, w = map(int, input().split())
    g = [[]for _ in range(n+1)]
    for __ in range(m):
        s, e, t = map(int, input().split())
        g[s].append((t, e))
        g[e].append((t, s))
    for __ in range(w):
        s, e, t = map(int, input().split())
        g[s].append((-t, e))

    for x in g:
        x.sort()

    r = 1
    for i in range(1, n+1):
        r *= dijkstra(g, i)
    if r:
        print('NO')
    else:
        print('YES')

jh05013 2년 전 0

데이터가 약해서 추가 요청을 올렸습니다.

https://www.acmicpc.net/board/...

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

문제

문제

출처

ICPC

다익스트라로 정답처리 됩니다.(정답코드 주의)

seungwuk98 2년 전 0

jh05013 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말