백준 온라인 저지, 최단경로 / 10282번: 해킹 (파이썬 / , 백준 골드문제)

문제

최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.

최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

• 첫째 줄에 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다(1 ≤ n ≤ 10,000, 1 ≤ d ≤ 100,000, 1 ≤ c ≤ n).
• 이어서 d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다(1 ≤ a, b ≤ n, a ≠ b, 0 ≤ s ≤ 1,000). 이는 컴퓨터 a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다.

각 테스트 케이스에서 같은 의존성 (a, b)가 두 번 이상 존재하지 않는다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 총 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간을 공백으로 구분지어 출력한다.

제한

예제 입력 1

2
3 2 2
2 1 5
3 2 5
3 3 1
2 1 2
3 1 8
3 2 4

예제 출력 1

2 5
3 6

힌트

W3sicHJvYmxlbV9pZCI6IjEwMjgyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNTc0XHVkMGI5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWNkNWNcdWQ3NDlcdWNkNWNcdWM1NDVcdWM3NTggXHVkNTc0XHVjZWU0IHl1bTNcdWM3NzQgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjIFx1YzJkY1x1YzEyNFx1Yzc1OCBcdWQ1NWMgXHVjZWY0XHVkNGU4XHVkMTMwXHViOTdjIFx1ZDU3NFx1ZDBiOVx1ZDU4OFx1YjJlNCEgXHVjNzc0XHVjODFjIFx1YzExY1x1Yjg1Y1x1YzVkMCBcdWM3NThcdWM4NzRcdWQ1NThcdWIyOTQgXHVjZWY0XHVkNGU4XHVkMTMwXHViNGU0XHVjNzQwIFx1YzgxMFx1Y2MyOCBcdWQ1NThcdWIwOThcdWI0NTggXHVjODA0XHVjNWZjXHViNDE4XHVhZTMwIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHVjNWI0XHViNWE0IFx1Y2VmNFx1ZDRlOFx1ZDEzMCBhXHVhYzAwIFx1YjJlNFx1Yjk3OCBcdWNlZjRcdWQ0ZThcdWQxMzAgYlx1YzVkMCBcdWM3NThcdWM4NzRcdWQ1NWNcdWIyZTRcdWJhNzQsIGJcdWFjMDAgXHVhYzEwXHVjNWZjXHViNDE4XHViYTc0IFx1YWRmOFx1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWM3N2NcdWM4MTUgXHVjMmRjXHVhYzA0IFx1YjRhNCBhXHViM2M0IFx1YWMxMFx1YzVmY1x1YjQxOFx1YWNlMCBcdWI5Y2NcdWIyZTQuIFx1Yzc3NFx1YjU0YyBiXHVhYzAwIGFcdWI5N2MgXHVjNzU4XHVjODc0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YmE3NCwgYVx1YWMwMCBcdWFjMTBcdWM1ZmNcdWI0MThcdWIzNTRcdWI3N2NcdWIzYzQgYlx1YjI5NCBcdWM1NDhcdWM4MDRcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2Q1Y1x1ZDc0OVx1Y2Q1Y1x1YzU0NVx1Yzc1OCBcdWQ1NzRcdWNlZTQgeXVtM1x1Yzc3NCBcdWQ1NzRcdWQwYjlcdWQ1NWMgXHVjZWY0XHVkNGU4XHVkMTMwIFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWFjMDEgXHVjNzU4XHVjODc0XHVjMTMxXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsIFx1ZDU3NFx1ZDBiOVx1YjJmOVx1ZDU1YyBcdWNlZjRcdWQ0ZThcdWQxMzBcdWFlNGNcdWM5YzAgXHVkM2VjXHVkNTY4XHVkNTU4XHVjNWVjIFx1Y2QxZCBcdWJhODcgXHViMzAwXHVjNzU4IFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1YWMwMCBcdWFjMTBcdWM1ZmNcdWI0MThcdWJhNzAgXHVhZGY4XHVjNWQwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVjNWJjXHViOWM4XHVjNzc4XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1Y2Q1Y1x1YjMwMCAxMDBcdWFjMWNcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2VmNFx1ZDRlOFx1ZDEzMCBcdWFjMWNcdWMyMTggbiwgXHVjNzU4XHVjODc0XHVjMTMxIFx1YWMxY1x1YzIxOCBkLCBcdWQ1NzRcdWQwYjlcdWIyZjlcdWQ1NWMgXHVjZWY0XHVkNGU4XHVkMTMwXHVjNzU4IFx1YmM4OFx1ZDYzOCBjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCgxICZsZTsgbiAmbGU7IDEwLDAwMCwgMSAmbGU7IGQgJmxlOyAxMDAsMDAwLCAxICZsZTsgYyAmbGU7IG4pLjxcL2xpPlxyXG5cdDxsaT5cdWM3NzRcdWM1YjRcdWMxMWMgZFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1Yzc1OFx1Yzg3NFx1YzEzMVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4IGEsIGIsIHNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0KDEgJmxlOyBhLCBiICZsZTsgbiwgYSAmbmU7IGIsIDAgJmxlOyBzICZsZTsgMSwwMDApLiBcdWM3NzRcdWIyOTQgXHVjZWY0XHVkNGU4XHVkMTMwIGFcdWFjMDAgXHVjZWY0XHVkNGU4XHVkMTMwIGJcdWI5N2MgXHVjNzU4XHVjODc0XHVkNTU4XHViYTcwLCBcdWNlZjRcdWQ0ZThcdWQxMzAgYlx1YWMwMCBcdWFjMTBcdWM1ZmNcdWI0MThcdWJhNzQgc1x1Y2QwOCBcdWQ2YzQgXHVjZWY0XHVkNGU4XHVkMTMwIGFcdWIzYzQgXHVhYzEwXHVjNWZjXHViNDI4XHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMFx1YzExYyBcdWFjMTlcdWM3NDAgXHVjNzU4XHVjODc0XHVjMTMxIChhLCBiKVx1YWMwMCBcdWI0NTAgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1Y2QxZCBcdWFjMTBcdWM1ZmNcdWI0MThcdWIyOTQgXHVjZWY0XHVkNGU4XHVkMTMwIFx1YzIxOCwgXHViOWM4XHVjOWMwXHViOWM5IFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1YWMwMCBcdWFjMTBcdWM1ZmNcdWI0MThcdWFlMzBcdWFlNGNcdWM5YzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVjOWMwXHVjNWI0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMDI4MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZhaWxpbmcgQ29tcG9uZW50cyIsImRlc2NyaXB0aW9uIjoiPHA+QXMgYSBqdXJ5IG1lbWJlciBvZiB0aGUgQmVzdCBBcmNoaXRlY3R1cmFsIFBsYW5uaW5nIENvbnRlc3QsIHlvdSBhcmUgdGFza2VkIHdpdGggc2NvcmluZyB0aGUgcmVsaWFiaWxpdHkgb2YgYSBzeXN0ZW0uIEFsbCBzeXN0ZW1zIGVudGVyZWQgaW4gdGhlIGNvbnRlc3QgY29uc2lzdCBvZiBhIG51bWJlciBvZiBjb21wb25lbnRzIHdoaWNoIGRlcGVuZCBvbiBlYWNoIG90aGVyLiBUaGUgcmVsaWFiaWxpdHkgb2Ygc3VjaCBhIHN5c3RlbSBkZXBlbmRzIG9uIHRoZSBkYW1hZ2UgZG9uZSBieSBhIGZhaWxpbmcgY29tcG9uZW50LiBJZGVhbGx5IGEgZmFpbGluZyBjb21wb25lbnQgc2hvdWxkIGhhdmUgbm8gY29uc2VxdWVuY2VzLCBidXQgc2luY2UgbW9zdCBjb21wb25lbnRzIGRlcGVuZCBvbiBlYWNoIG90aGVyLCBzb21lIG90aGVyIGNvbXBvbmVudHMgd2lsbCB1c3VhbGx5IGZhaWwgYXMgd2VsbC48XC9wPlxyXG5cclxuPHA+TW9zdCBjb21wb25lbnRzIGFyZSBzb21ld2hhdCByZXNpbGllbnQgdG8gc2hvcnQgZmFpbHVyZXMgb2YgdGhlIGNvbXBvbmVudHMgdGhleSBkZXBlbmQgb24uIEZvciBleGFtcGxlLCBhIGRhdGFiYXNlIGNvdWxkIGJlIHVuYXZhaWxhYmxlIGZvciBhIG1pbnV0ZSBiZWZvcmUgdGhlIGNhY2hlcyBleHBpcmUgYW5kIG5ldyBkYXRhIG11c3QgYmUgcmV0cmlldmVkIGZyb20gdGhlIGRhdGFiYXNlLiBJbiB0aGlzIGNhc2UsIHRoZSBjYWNoZXMgY2FuIHN1cnZpdmUgZm9yIGEgbWludXRlIGFmdGVyIGEgZGF0YWJhc2UgZmFpbHVyZSwgYmVmb3JlIGZhaWxpbmcgdGhlbXNlbHZlcy4gSWYgYSBjb21wb25lbnQgZGVwZW5kcyBvbiBtdWx0aXBsZSBvdGhlciBjb21wb25lbnRzIHdoaWNoIGZhaWwsIGl0IHdpbGwgZmFpbCBhcyBzb29uIGFzIGl0IGNhbiBubyBsb25nZXIgc3Vydml2ZSB0aGUgZmFpbHVyZSBvZiBhdCBsZWFzdCBvbmUgb2YgdGhlIGNvbXBvbmVudHMgaXQgZGVwZW5kcyBvbi4gRnVydGhlcm1vcmUgbm8gY29tcG9uZW50IGRlcGVuZHMgb24gaXRzZWxmIGRpcmVjdGx5LCBob3dldmVyIGluZGlyZWN0IHNlbGYtZGVwZW5kZW5jeSB0aHJvdWdoIG90aGVyIGNvbXBvbmVudHMgaXMgcG9zc2libGUuPFwvcD5cclxuXHJcbjxwPllvdSB3YW50IHRvIGtub3cgaG93IG1hbnkgY29tcG9uZW50cyB3aWxsIGZhaWwgd2hlbiBhIGNlcnRhaW4gY29tcG9uZW50IGZhaWxzLCBhbmQgaG93IG11Y2ggdGltZSBwYXNzZXMgYmVmb3JlIGFsbCBjb21wb25lbnRzIHRoYXQgd2lsbCBldmVudHVhbGx5IGZhaWwsIGFjdHVhbGx5IGZhaWwuIFRoaXMgaXMgZGlmZmljdWx0IHRvIGNhbGN1bGF0ZSBieSBoYW5kLCBzbyB5b3UgZGVjaWRlZCB0byB3cml0ZSBhIHByb2dyYW0gdG8gaGVscCB5b3UuIEdpdmVuIHRoZSBkZXNjcmlwdGlvbiBvZiB0aGUgc3lzdGVtLCBhbmQgdGhlIGluaXRpYWwgY29tcG9uZW50IHRoYXQgZmFpbHMsIHRoZSBwcm9ncmFtIHNob3VsZCByZXBvcnQgaG93IG1hbnkgY29tcG9uZW50cyB3aWxsIGZhaWwgaW4gdG90YWwsIGFuZCBob3cgbXVjaCB0aW1lIHBhc3NlcyBiZWZvcmUgYWxsIHRob3NlIGNvbXBvbmVudHMgaGF2ZSBhY3R1YWxseSBmYWlsZWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCB0aHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgbiwgZCBhbmQgYyAoMSAmbGU7IG4gJmxlOyAxMCAwMDAgYW5kIDEgJmxlOyBkICZsZTsgMTAwIDAwMCBhbmQgMSAmbGU7IGMgJmxlOyBuKTogdGhlIHRvdGFsIG51bWJlciBvZiBjb21wb25lbnRzIGluIHRoZSBzeXN0ZW0sIHRoZSBudW1iZXIgb2YgZGVwZW5kZW5jaWVzIGJldHdlZW4gY29tcG9uZW50cywgYW5kIHRoZSBpbml0aWFsIGNvbXBvbmVudCB0aGF0IGZhaWxzLCByZXNwZWN0aXZlbHkuPFwvbGk+XHJcblx0PGxpPmQgbGluZXMgd2l0aCB0aHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgYSwgYiBhbmQgcyAoMSAmbGU7IGEsIGIgJmxlOyBuIGFuZCBhICZuZTsgYiBhbmQgMCAmbGU7IHMgJmxlOyAxIDAwMCksIGluZGljYXRpbmcgdGhhdCBjb21wb25lbnQgYSBkZXBlbmRzIG9uIGNvbXBvbmVudCBiLCBhbmQgY2FuIHN1cnZpdmUgZm9yIHMgc2Vjb25kcyB3aGVuIGNvbXBvbmVudCBiIGZhaWxzLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkluIGVhY2ggdGVzdCBjYXNlLCBhbGwgZGVwZW5kZW5jaWVzIChhLCBiKSBhcmUgdW5pcXVlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiB0aGUgdG90YWwgbnVtYmVyIG9mIGNvbXBvbmVudHMgdGhhdCB3aWxsIGZhaWwsIGFuZCB0aGUgbnVtYmVyIG9mIHNlY29uZHMgYmVmb3JlIGFsbCBjb21wb25lbnRzIHRoYXQgd2lsbCBmYWlsLCBoYXZlIGFjdHVhbGx5IGZhaWxlZC48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

접근 방법

- 다익스트라 최단경로 알고리즘을 통해 한 컴퓨터로부터 해킹할 수 있는 컴퓨터개수와 그 최대 시간을 출력한다.

코드

# 접근 방법
# 다익스트라 최단경로 알고리즘을 통해 한 컴퓨터로부터 해킹할 수 있는 컴퓨터개수와 그 최대 시간을 출력한다.
def dijkstra(start):
    time[start] = 0
    q = []
    heapq.heappush(q, [0, start])
    while q:
        t, now = heapq.heappop(q)
        if time[now] < t:
            continue
        
        for next, sec in graph[now]:
            cost = t + sec
            if time[next] > cost:
                heapq.heappush(q, [cost, next])
                time[next] = cost


import heapq, sys
input = sys.stdin.readline
for tc in range(int(input())):
    n, d, c = map(int, input().split())
    INF = int(1e9)
    time = [INF for _ in range(n+1)]
    graph =[[] for _ in range(n+1)]
    for _ in range(d):
        a, b, s = map(int, input().split())
        graph[b].append([a, s])
    
    dijkstra(c)
    print(sum(1 for x in time if x < INF), max([x for x in time if x