간선 이어가기 2

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

"""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()

• Dependency
  • teflib.graph.create_wgraph_from_input
  • teflib.graph.shortest_paths