PLOD

문제 상황도시들이 도로로 연결되어 있고, 매 도로에서 퍼레이드가 열릴 수 있다. 퍼레이드가 열리면 해당 도로를 사용할 수 없게 되는데, 이 때 최단 경로가 영향을 받는 정점쌍(s, t)의 개수를 각 도로별로 구하는 문제다.단순히 보면, 도로 하나씩 막고 다익스트라를 돌리면 될 것 같지만, 그렇게 하면 시간 초과가 발생할 수 있다.어떤 시도를 했는지첫 시도: 각 도로를 하나씩 제거하고 다익스트라를 수행한 뒤, 원래의 최단 경로보다 멀어진 정점들을 확인해 카운트하는 브루트포스 방식으로 구현했다.성공은 했지만 비효율적: Python에서 다익스트라를 M번 반복하는 방식은 입력 수가 많아질수록 매우 느려졌다.작성 코드# https://www.acmicpc.net/problem/16118import sys, hea..