Informatica Online Judge

  학교 가는 길#1 [1790 / 06FE]

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


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

[koistudy.net (34st 조승한)]

Background

태영이는 최근 게임중독에 빠져서, 시간만 남으면 피씨방에 가는 등 나쁜(?) 짓을 한다. 어느 수요일, 태영이는 R&E를 끝내고 학교로 돌아오는 길에 피씨방에 가고 싶어졌다.

태영이가 사는 도시는 N개의 지점이 있다. 그 지점은 1~N으로 나타낼 수 있으며, 한쪽 방향으로만 이동할 수 있는 M개의 도로로 연결되어 있다. 이 도시는 순환(사이클)이 생기는 도로는 한개도 주어지지 않는다. (예를 들면 1->2 2->3 3->1)

태영이가 R&E를 끝낸 대학교는 1번 지점이고, 학교인 N번 지점으로 가고 싶어한다. 그 외 지점들은 모두 피씨방이며, 태영이는 학교로 돌아오는 길에 최대한 많은 피씨방에 들르고 싶다.

하지만, 저녁시간이 넘어서 들어가게 된다면 사감선생님에게 크게 혼나게 되므로, 저녁시간 전에 들어가고자 한다.

i번째 도로를 지날 때 걸리는 시간은 ti, i번째 지점(피씨방)에 도착하게 되면 쓰는 시간은 ci로 입력에 주어진다.

태영이가 제 시간 T안에 학교에 도착하고, 최대한 많은 피씨방에 들를 수 있게 도와주자.

Input

입력의 1번째 줄은 세 개의 정수 N, M, T로 이루어져 있다. (2 <= N <= 5,000, 1 <= M <= 5,000, 1 <= T <= 1,000,000,000) - 지점의 개수, 도로의 개수, 저녁시간까지 남은 시간.

입력의 2번째 줄부터 M+1번째 줄은 도로를 뜻하며, 세 개의 정수 ui, vi, ti로 이루어져 있다. (1 <= ui, vi <= N, ui != vi, 1 <= ti <= 1,000,000,000) - 도로의 시작점, 끝점, 가는 데 걸리는 시간. 도로는 단방향이며 (끝점에서 시작점으로 가지 못함), 순환(사이클)이 생기지 않는다.

입력의 마지막 줄은 N개의 정수 ci 로 이루어져 있다. (1 <= ci <= 1,000,000,000) - 그 지점에 도착하였을 때 소비하게 되는 시간.

[입력값의 정의역]
Subtask #1 : N개의 지점은 일직선으로 이루어져 있으며, 반드시 길이 존재한다.
Subtask #2 : $2 <= N <= 20, 1 <= M <= 20$
Subtask #3 : $2 <= N <= 5,000, 1 <= M <= 5,000$

Output

출력의 1번째 줄은 한 개의 정수 K를 출력한다. (2 <= K <= N) - 태영이가 들를 수 있는 최대 지점 수.

출력의 2번째 줄은 한 개의 정수 L을 출력한다. (0 <= L <= T) - 태영이가 최대한 많은 피씨방에 들러 학교에 도착하였을 때, 걸리는 시간.

만약 시간 안에 학교로 도착할 수 없거나, 학교로 가는 길이 존재하지 않는다면 –1 한 줄만 출력하고, L이 될 수 있는 값이 여러 개라면 가장 작은 값을 출력하여라.

이 K는 학교와 R&E를 끝낸 대학교를 포함한다는 것에 유의하라.

IO Example

입력
5 6 8
1 4 1
1 3 2
1 2 1
3 5 3
4 5 3
2 3 5
0 3 2 4 0

출력
3
7

예제 설명



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