신제품 개발

• 기본적으로는 각각의 이동을 하나씩 처리하는 시뮬레이션을 돌린다. 시간 단축은, 이동 경로가 사이클을 이루게 되면 그래프가 변경될때까지 사이클을 따라 x번 이동하는 것을 한번에 처리해줌으로써 가능하다.
• 그래프의 변경되기 이전까지의 시뮬레이션은, O(N)번 이동에 사이클을 찾아내면, 그 이후의 사이클의 반복횟수를 계산해서 그만큼 값을 업데이트해주는 것은 O(1)에 처리된다. 그래프는 최대 M번 변경되므로, 총 시간복잡도는 O(NM)이다.
• 이론은 간단한데, 구현이 좀 까다롭다. 우선 그래프를 일반 그래프 형태로 관리할 필요는 없고, 각 노드들마다 현재 c값 기준의 넥스트 노드만을 저장하고 있도록 관리하면 된다. c값이 증가해서 그래프의 변경이 일어나면, 해당되는 노드들의 넥스트 노드들을 업데이트 해주면 된다. c값이 증가할때 변경해야될 엣지들을 쉽게 찾기 위해서, 모든 엣지들을 B값 순서로 정렬해서 갖고 있으면 된다.
• 사이클이 생길때까지 이동하다가 그래프가 변경되면, 변경된 점을 다시 출발점으로 삼아서 사이클을 찾기 시작한다. 사이클을 찾게 되었다면, 그래프의 변경 없이 사이클을 돌릴수 있는 횟수는, ({다음으로 큰 B값} - {현재의 c값}) / {사이클을 한번 돌때 증가되는 c값} 이 된다. 이 횟수만큼 사이클을 돌리고 나면, 다시 현재 점을 출발점으로 삼아서 사이클을 찾기 시작한다.
• 기본적인 구현 사항도 쉽지 않지만, 추가로 신경써야 할 부분들이 더 있다.
  • 사이클을 돌다가도 이동 횟수가 K번이 되면 멈춰야 한다
  • A값이 0인 노드들도 있다. 사이클을 한번 돌때 증가되는 c값이 0인 경우도 생각해야 한다
  • c값을 그냥 계속 누적시키면 64bit 정수범위를 초과할수 있다. 다행히 파이썬에서는 신경쓰지 않아도 된다.
  • 시간제한이 빡빡하다 (파이썬 추가시간이 없다). 이대로 그냥 구현하면, 파이썬으로는 시간초과를 받을수 있다.
• 시간제한에 관련해서는, 좀더 상수 최적화를 시켜야만 pypy로 겨우 통과한다.
  • 생각할 수 있는 최적화들이 여럿 있지만, 내 경험상 가장 결정적으로 작용했던것은, 사이클을 찾고 난 뒤에 사이클을 돌릴 횟수를 구할때, 다음으로 그래프가 변경될때까지 사이클을 돌리는 것이 아니라, 사이클에 포함되는 노드의 엣지가 변경될때까지 사이클을 돌리는 것이다. 사이클에 포함되지 않는 노드의 엣지는 변경되더라도 사이클을 돌리는데에는 영향을 받지 않기 때문이다. 이것을 적용해서 구현함으로써 간신히 TLE에서 1000ms 정도로 통과시킬수 있었다.

"""Solution code for "BOJ 31250. 신제품 개발".

- Problem link: https://www.acmicpc.net/problem/31250
- Solution link: http://www.teferi.net/ps/problems/boj/31250

Tags: [simulation]
"""

import sys

SOURCE = 0
MOD = 1_000_000_007
INF = float('inf')


def main():
    N, M, K = [int(x) for x in sys.stdin.readline().split()]
    A = [int(x) for x in sys.stdin.readline().split()]
    edges = [(INF, N, N)]
    for _ in range(M):
        u, v, B = [int(x) for x in sys.stdin.readline().split()]
        edges.append((B, u - 1, v - 1))

    edges.sort(reverse=True)
    c, u = 0, SOURCE
    move_count = K
    successors = list(range(N))
    order, inc_sum = [-1] * (N + 1), [-1] * (N + 1)
    order[N] = INF
    order[u] = cur_order = path_beg = 0
    inc_sum[u] = cur_inc_sum = 0

    if edges[-1][0] == 0:
        _, x, y = edges.pop()
        successors[x] = y

    while move_count:
        move_count -= 1
        u = successors[u]
        c += A[u]
        cur_order += 1
        cur_inc_sum += A[u]

        if c >= edges[-1][0]:
            while c >= edges[-1][0]:
                _, x, y = edges.pop()
                successors[x] = y
            path_beg = cur_order
            cur_inc_sum = 0

        if order[u] >= path_beg:
            cycle_beg = order[u]
            while order[edges[-1][1]] < cycle_beg:
                _, x, y = edges.pop()
                successors[x] = y

            next_b = edges[-1][0]
            cycle_inc = cur_inc_sum - inc_sum[u]
            cycle_size = cur_order - order[u]
            if cycle_inc == 0 or next_b == INF:
                cycle_count = move_count // cycle_size
            else:
                cycle_count = min(
                    (next_b - c) // cycle_inc, move_count // cycle_size
                )
            c += cycle_inc * cycle_count
            move_count -= cycle_size * cycle_count

            if c == next_b:
                _, x, y = edges.pop()
                successors[x] = y
            path_beg = cur_order
            cur_inc_sum = 0

        order[u], inc_sum[u] = cur_order, cur_inc_sum

    print(u + 1, c % MOD)


if __name__ == '__main__':
    main()