아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

늑대 왕 그러프

면접 대비

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

요약
각 쿼리마다 총 길이가 D 이하인 A에서 B 경로에 포함된 도로의 폐쇄 비용 합을 구합니다.
난이도

보통10점 중 6점

유형
최단 경로, 정렬, 누적 합
정답자
아직 제출이 없습니다

문제

늑대 왕 그러프는 N개 도시와 M개의 일방통행 도로가 있는 나라를 다스립니다. i번 도로는 Xi에서 Yi로 가며 길이 Li, 폐쇄 비용 Ci가 있습니다. 두 도시 A와 B 사이를 불편하게 만들기 위해 거리 한도 D를 정하고, A에서 B까지 길이가 D 이하인 경로에 포함되는 모든 도로를 동시에 폐쇄합니다. Q개의 서로 다른 D 값마다 필요한 총 폐쇄 비용을 구하세요.

입력

첫 줄에 N, M, A, B가 있습니다. 다음 M줄에 Xi, Yi, Li, Ci가 주어집니다. 그다음 Q가 있고, Q줄에 각 Di가 주어집니다.

출력

각 Di에 대해 폐쇄해야 하는 도로의 비용 합을 한 줄씩 출력합니다.

예제2

  1. 예제 1

    입력
    4 5 1 3
1 2 5 1
1 2 8 50
2 3 2 15
3 1 80 1000
3 4 1 1
4
8
6
90
94
    예상 출력
    16
0
66
1066

  2. 예제 2

    입력
    4 3 1 2
2 1 1 1
3 4 10000 10000
4 3 10000 10000
1
1000000000
    예상 출력
    0