Informatica Online Judge

  빚쟁이 민규 #1 [2373 / 0945]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 2   Total Tried : 2


The Champion of this Problem (C++) : gs18113 - ms / 1755byte
My Best Submission (C++) : N/A

[36th 최승민(gs18113)]
Writer ID : [gs18113]

Background

귀여운 민규는 같은 학교 학생인 준호에게 10000원을 빌렸다. 그러나, 민규가 일주일이 지나도록 도통 돈을 갚으려고 하지 않자 화가 난 준호는 민규를 만날 때마다 독촉하기 시작했다. 하지만 이번 달 용돈을 다 써 버린 민규는 준호에게 줄 돈을 아직 준비하지 못했다. 준호의 독촉에 지쳐버린 민규는, 돈을 갚는 대신 준호를 계속해서 피해 다닌다는 전략을 쓰기로 하였다.

하지만, 민규의 이런 전략에는 큰 문제가 있었다. 준호와 민규의 집이 같은 마을에 있다는 것이다! 민규는 학교가 있는 마을과 자신이 사는 마을에 대해서는 능통하기 때문에 이곳들에서는 준호를 피할 수 있지만, 그 외의 마을에서는 준호를 피할 자신이 없다. 민규가 귀갓길에 준호에게 또 발각된다면, 민규는 준호에게 어떤 일을 당할지 모른다! 우리 모두 민규의 안전을 위해, 민규와 준호가 귀갓길에 마주치지 않을 경우의 수를 구해주자.

민규와 준호가 사는 도시는 총 $N$개의 마을로 구성되어 있다. 민규와 준호가 다니는 학교는 1번 마을에 세워져 있으며, 집은 둘 다 $N$번 마을에 위치하고 있다. 각 마을을 잇는 도로는 총 $M$개가 존재하며, 양방향 통행이 가능하고, $i$번째 도로를 건너는 데 $T_i$ 시간이 걸린다. 또한, 민규와 준호는 극한의 효율성을 추구하기 때문에, 둘 다 항상 최단거리 경로로 집에 간다고 하자. 이때 민규와 준호가 만나지 않는 경로의 순서쌍의 개수를 구하는 프로그램을 작성하시오. 단, 여기서 만난다는 것은 둘의 경로가 1, $N$을 제외한 마을을 적어도 하나 공유한다는 것을 뜻한다.

답이 클 수 있으니 $10^9+7$로 나눈 나머지를 출력하시오.

예를 들어, 민규가 사는 도시가 아래와 같이 생겼다고 하자.
그러면 학교(마을 1)에서 집(마을 8)까지 가는 경로는 총 5개가 있고, 그 중 1, $N$을 제외한 마을을 공유하지 않는 경로 순서쌍은 총 2개이다.

Input

첫 번째 줄에 $N$, $M$이 공백으로 구분되어 입력된다.

두 번째 줄부터 $M+1$번째 줄까지, 수 $S_i$, $E_i$, $T_i$($1\leq i\leq M$) 가 공백으로 구분되어 입력된다. $S_i$와 $E_i$는 i번째 도로의 양쪽 끝 마을의 번호를 의미하며, $T_i$는 $i$번째 도로를 건너는 데 드는 시간을 의미한다. $T_i$는 1이상 $10^9$이하의 정수이다.


[제한 조건]

$2\leq N\leq 5000$

$N-1\leq M\leq 5000$

1번 마을에서 N번 마을로 가는 경로는 항상 존재한다.

Subtask 1: (this problem)

모든 도로를 건너는 데 걸리는 시간은 1로 일정하다.

Subtask 2:

추가적인 제한 조건이 없다.

Output

민규와 준호의 경로가 겹치지 않는 경우의 수를 $10^9+7$로 나눈 나머지를 출력한다.

IO Example

입력
8 12
1 2 1
2 3 1
2 5 1
3 7 1
8 7 1
1 4 1
4 5 1
3 5 1
5 7 1
5 6 1
6 7 1
6 8 1

출력
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]