오민식의 고민

시간 제한2초메모리 제한128 MB

요약
도시 A에서 B까지 이동하며 방문 시 얻는 금액과 이동 비용을 고려해 도착 시 최대 금액을 구하고, 양의 순환으로 무한히 증가하는 경우를 판별합니다.
난이도

보통10점 중 7점

유형
그래프, 최단 경로, 동적 계획법, DFS
정답자
아직 제출이 없습니다

문제

오민식은 물건을 팔기 위해 여러 도시를 이동한다. 이 나라에는 0번부터 N-1번까지 번호가 붙은 N개의 도시가 있고, 여행은 시작 도시 A에서 출발해 도착 도시 B에서 끝난다.

오민식이 이용할 수 있는 교통수단은 여러 개이며, 각 교통수단은 출발 도시, 도착 도시, 이용 비용이 정해져 있다. 모든 교통수단은 주어진 방향으로만 이용할 수 있고, 같은 교통수단을 여러 번 이용해도 된다.

각 도시에는 방문할 때마다 벌 수 있는 금액이 정해져 있다. 같은 도시를 여러 번 방문하면 그때마다 다시 돈을 번다.

오민식은 도착 도시 B에 도착했을 때 가지고 있는 돈을 최대화하려고 한다. 교통비가 번 돈보다 크면 최댓값이 음수가 될 수도 있다. 도착 도시에서 가질 수 있는 돈의 최댓값을 구하시오.

입력

첫째 줄에 도시의 수 N, 시작 도시 A, 도착 도시 B, 교통수단의 개수 M이 주어진다.

다음 M개의 줄에는 교통수단 정보가 시작 끝 가격 형식으로 주어진다.

마지막 줄에는 0번 도시부터 N-1번 도시까지, 각 도시를 방문할 때마다 벌 수 있는 금액이 차례대로 주어진다.

N과 M은 50 이하이다. 도시에서 벌 수 있는 금액과 교통수단의 가격은 1,000,000 이하의 음이 아닌 정수이다.

출력

도착 도시 B에 도착할 수 없다면 gg를 출력한다.

도착 도시 B에 도착하면서 가질 수 있는 돈을 무한히 크게 만들 수 있다면 Gee를 출력한다.

그 외에는 도착 도시 B에 도착했을 때 가질 수 있는 돈의 최댓값을 출력한다.

예제6

  1. 예제 1

    입력
    5 0 4 7
0 1 13
1 2 17
2 4 20
0 3 22
1 3 4747
2 0 10
3 4 10
0 0 0 0 0
    예상 출력
    -32

  2. 예제 2

    입력
    5 0 4 5
0 1 10
1 2 10
2 3 10
3 1 10
2 4 10
0 10 10 110 10
    예상 출력
    Gee

  3. 예제 3

    입력
    3 0 2 3
0 1 10
1 0 10
2 1 10
1000 1000 47000
    예상 출력
    gg

  4. 예제 4

    입력
    2 0 1 2
0 1 1000
1 1 10
11 11
    예상 출력
    Gee

  5. 예제 5

    입력
    1 0 0 1
0 0 10
7
    예상 출력
    7

  6. 예제 6

    입력
    5 0 4 7
0 1 13
1 2 17
2 4 20
0 3 22
1 3 4747
2 0 10
3 4 10
8 10 20 1 100000
    예상 출력
    99988