사용자 도구

사이트 도구


ps:problems:boj:14284

간선 이어가기 2

ps
링크acmicpc.net/…
출처BOJ
문제 번호14284
문제명간선 이어가기 2
레벨골드 5
분류

최단 경로

시간복잡도O(ElogV)
인풋사이즈E<100,000, V<=5000
사용한 언어Python 3.11
제출기록46736KB / 184ms
최고기록180ms
해결날짜2024/02/23

풀이

  • 설명을 살짝 꼬아놓았지만, 결국은 두 점 사이의 최단 경로의 길이를 구하라를 문제이다.
  • 가중치가 양수이므로 그냥 데이크스트라를 돌려서 구해주면 끝.
  • 문제에서는 중복 엣지가 존재하지 않는다는 조건이 따로 없으므로 이것을 고려해줘야 할것 같은데, 고려하지 않고 짜도 잘 통과된다.

코드

"""Solution code for "BOJ 14284. 간선 이어가기 2".

- Problem link: https://www.acmicpc.net/problem/14284
- Solution link: http://www.teferi.net/ps/problems/boj/14284

Tags: [dijkstra]
"""

import sys
from teflib import graph as tgraph


def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]
    wgraph = tgraph.create_wgraph_from_input(n, m, dup_edge_selector_func=min)
    s, t = [int(x) - 1 for x in sys.stdin.readline().split()]

    print(tgraph.shortest_paths(wgraph, s, dest=t)[t])


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
G L C N A
 
ps/problems/boj/14284.txt · 마지막으로 수정됨: 2024/02/23 01:24 저자 teferi