레이팅 미적용베시와 농부 존은 염소 카트 경주를 즐긴다. 이는 다른 이들이 즐기는 고카트 경주와 매우 비슷하지만, 카트를 염소가 끌고 트랙이 근처 농지로 만들어진다는 점이 다르다. 농지는 \(N\)개의 초원과, 각각 초원 쌍을 연결하는 \(M\)개의 길로 이루어져 있다.
베시는 근처 농장들로 코스를 만들고 싶다. 농장이란 두 개 이상의 초원으로 이루어진 부분집합으로, 그 안의 모든 초원이 서로 유일한 길의 순서를 따라 도달할 수 있는 것을 말한다.
근처 농지에는 여러 농장이 있을 수 있다. 농장이 \(K\)개 있다고 하자. 베시는 길이 \(X\)인 길 \(K\)개를 추가하여 \(K\)개의 농장을 모두 연결해 염소 카트 순환 코스를 만들고 싶다. 각 농장은 정확히 한 번씩 방문되어야 하며, 각 농장 안에서는 적어도 하나의 길을 지나가야 한다.
경주자들에게 흥미로운 코스가 되려면 트랙의 총 길이가 적어도 \(Y\) 이상이어야 한다. 베시는 그러한 모든 흥미로운 트랙에 대해 트랙 총 길이의 합을 알고 싶다. 어떤 트랙이 다른 트랙과 다르다는 것은, (농장 간 길을 추가한 후) 한 트랙에서는 인접하지만 다른 트랙에서는 인접하지 않은 두 초원이 존재한다는 뜻이다. 선택된 길만이 중요하며, 염소 카트가 그 길들을 지나는 방향은 중요하지 않다는 점에 유의하라.
문제 제공: Matt Fontaine
문제 제공: Matt Fontaine
첫째 줄에 \(N\), \(M\), \(X\), \(Y\)가 주어지며, \(1 \leq N \leq 1500\), \(1 \leq M \leq N-1\), \(0 \leq X, Y \leq 2500\)이다.
다음 \(M\)개의 줄은 길을 나타낸다. 각 줄은 \(A_i\) \(B_i\) \(D_i\) 형태로, 초원 \(A_i\)와 \(B_i\)가 정수 길이 \(D_i\)의 길로 연결되어 있음을 의미한다 (\(1 \leq A_i, B_i \leq N\), \(0 \leq D_i \leq 2500\)). 각 초원은 적어도 하나의 길과 인접하며, 길로 이루어진 사이클은 존재하지 않는다.
적어도 70%의 테스트 케이스에서는 추가로 \(N \leq 1000\)과 \(Y \leq 1000\)이 보장된다.
모든 흥미로운 트랙에 대한 트랙 길이의 합을 나타내는 정수 하나를 출력한다. 트랙 길이의 합이 매우 클 수 있으므로, 합을 \(10^9+7\)로 나눈 나머지를 출력한다.
mooriokart.in · 출력을 쓸 파일 mooriokart.out5 3 1 12
1 2 3
2 3 4
4 5 654This example has 6 possible tracks
1 --> 2 --> 4 --> 5 --> 1 (length 11)
1 --> 2 --> 5 --> 4 --> 1 (length 11)
2 --> 3 --> 4 --> 5 --> 2 (length 12)
2 --> 3 --> 5 --> 4 --> 2 (length 12)
1 --> 2 --> 3 --> 4 --> 5 --> 1 (length 15)
1 --> 2 --> 3 --> 5 --> 4 --> 1 (length 15)
The answer is \(12+12+15+15=54\), adding up only the tracks where the length is at
least \(12\).
Note that for this problem, the standard time limit is increased to 3 seconds
per test case (6 seconds per case for Java and Python).
riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > February > Platinum