시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB (추가 메모리 없음) | 602 | 279 | 223 | 49.336% |
연두는 방금 "플로이드 와샬 알고리즘"을 공부했다. 이 알고리즘은 $N$개의 정점으로 이루어진 그래프에서, 모든 정점 쌍의 최단 거리를 $O(N^3)$에 구해준다.
신이 난 연두는 자신이 좋아하는 그래프를 하나 가져왔다. 이 그래프는 $N$개의 정점과 $M$개의 양방향 간선으로 이루어진 단순 연결 그래프이며, 정점에는 $1, 2, \dots, n$으로 번호가 매겨져있다. 또한 딱 하나의 간선에만 $1$의 가중치가 있고 나머지 간선은 가중치가 $0$이다.
이제 이 그래프에서 모든 정점 쌍의 최단 거리의 합을 구해보려고 한다. 즉, $1 \le i < j \le N$를 만족하는 모든 $\frac{N(N-1)}{2}$개의 쌍 $(i,j)$에 대해, $i$번 정점과 $j$번 정점간의 최단거리를 전부 더한 값을 구할 것이다.
연두는 신나서 코드를 짰지만 한참 동안 기다려도 결과가 나오지 않았다. 절망에 빠진 연두는 더 좋은 방법을 생각해 냈는데, 바로 대회에 이 문제를 출제하여 여러분들이 답을 대신 구하게 하는 것이다.
첫 번째 줄에 정점의 개수 $N$($2 \le N \le 100\,000$), 간선의 개수 $M$($1 \le M \le 200\,000$), 정수 $K$($1 \le K \le M$)가 주어진다.
다음 $M$개의 줄에 걸쳐 $u_i$와 $v_i$가 주어진다. 이것은 $i$번째 간선은 $u_i$와 $v_i$를 잇는다는 것을 의미한다. ($1 \le u_i, v_i \le n, u_i \ne v_i$)
단순 연결 그래프만 입력으로 주어지며, $K$번째 간선의 가중치는 $1$이고, 나머지 간선의 가중치는 $0$이다.
모든 정점 쌍의 최단 거리의 합을 출력한다.
출력의 값이 32비트형 정수(C/C++의 int)의 최댓값을 넘을 수 있음에 주의하자.
5 4 2 1 2 2 3 3 4 4 5
6
각 정점 쌍에 대한 최단거리는 다음과 같다
3 3 1 1 2 2 3 3 1
0
단순 연결 그래프란 다음 조건들을 모두 만족하는 그래프를 의미한다.
University > 홍익대학교 > 2021 홍익대학교 프로그래밍 경진대회 E번