경유 이득 노선
골드 III의견: 0
\(N\)개의 도시가 있고, 도시 사이에 단방향 도로 \(M\)개가 있다. 도로 "\(a\) \(b\) \(w\)" 는 도시 \(a\)에서 \(b\)로 가는 길이 \(w\)짜리 도로를 뜻한다. 같은 방향으로 두 도시 사이에 도로가 여러 개 있을 수 있다.
서로 다른 두 도시 \(i\), \(j\)에 대해, \(i\)에서 \(j\)로 가는 최단 경로가 (도로를 직접 하나만 타는 것보다) 다른 도시를 거쳐 가는 편이 더 짧거나, 직접 도로가 아예 없는데도 거쳐서 도달 가능한 경우, 이 순서쌍 \((i, j)\)를 "경유 이득 쌍"이라 부른다.
정확히 말하면, \(i \ne j\) 이고 \(i\)에서 \(j\)로 도달 가능하며, 최단 거리가 \(i \to j\) 직접 도로 중 가장 짧은 것보다 엄격히 작은 (직접 도로가 없으면 무조건 포함) 순서쌍 \((i, j)\)의 개수를 구하여라.
\(2 \le N \le 200\), \(1 \le M \le 50{,}000\). 같은 \((a, b)\) 방향으로 도로가 여러 개일 수 있으며, 자기 자신으로의 도로는 없다.
첫째 줄에 도시 수 \(N\)과 도로 수 \(M\)이 주어진다. 이어 \(M\)개의 줄에 각각 세 정수 \(a\), \(b\), \(w\)가 주어진다 (\(1 \le a, b \le N\), \(a \ne b\), \(1 \le w \le 10^6\)).
경유 이득 쌍 \((i, j)\)의 개수를 한 줄에 출력한다.
3 3
1 2 5
2 3 1
1 3 10
11에서 3으로 직접 가면 10이지만, 2를 거치면 \(5+1=6\) 으로 더 짧다. 따라서 \((1,3)\) 은 경유 이득 쌍이다. 다른 쌍은 직접 도로가 최단이거나 도달 불가이므로 정답은 1이다.
2 1
1 2 4
01에서 2로 가는 길은 직접 도로 하나뿐이고 그것이 최단이며, 2에서 1로는 도달할 수 없다. 경유 이득 쌍이 없으므로 0이다.
riseoj 작성
출처 Original
평가 및 의견
경유 이득 노선
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
경유 이득 노선