백준 1240번, 노드사이의 거리 풀이
문제 백준 1240번 풀이 나가는 간선의 개수가 $ N - 1 $이고, 정점의 개수가 $ N $이므로 SPFA를 통해 구현하는 경우 최악의 시간 복잡도는 $ O(N^2) $이 됩니다. 테스트케이스의 개수가 $ M (\leq 1000) $이므로 최악의 경우 $ O(MN^2) $이 되어 TLE가 날 것 같이 생겼습니다. 하지만, 같은 그래프에 대해서 그러한 최악의 경우가 $ M $개가 되는 경우는 없다는 믿음을 가지고 SPFA를 사용하여 구현해봅시다. 16ms에 AC가 나오는 것을 볼 수 있습니다. 소스코드 #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pai..
2020.11.15