문제
N개의 정점과 M개의 단방향 간선으로 이루어진 그래프가 있다.
i번 간선은 정점 Ui에서 정점 Vi로 향하며, 길이는 Ci이다.
또한, i번 간선을 뒤집는 비용은 Di이다.
간선을 뒤집는다는 것은 정점 Ui에서 정점 Vi로 향하는 간선을 정점 Vi에서 정점 Ui로 향하는 간선으로 교체하는 것이다.
최대 한 개의 간선을 뒤집어서, (1번 정점에서 N번 정점으로 가는 최단경로의 길이) + (N번 정점에서 1번 정점으로 가는 최단경로의 길이) + (간선을 뒤집는 비용)의 최솟값을 구하여라.
입력
1번 줄 : N M
2번 ~ M + 1번 줄 : Ui Vi Ci Di
- 2 ≤ N ≤ 200
- 1 ≤ M ≤ 50 000
- 1 ≤ Ui, Vi ≤ N
- 0 ≤ Ci ≤ 1 000 000
- 0 ≤ Di ≤ 1 000 000 000
출력
최대 한 개의 간선을 뒤집을 때, (1번 정점에서 N번 정점으로 가는 최단경로의 길이) + (N번 정점에서 1번 정점으로 가는 최단경로의 길이) + (간선을 뒤집는 비용)의 최솟값을 첫 번째 줄에 출력하여라.
만약 어떤 간선을 뒤집더라도 1번 정점에서 N번 정점으로 가는 경로와 N번 정점에서 1번 정점으로 가는 경로가 동시에 존재하지 않는다면 "-1"(쌍따옴표 제외)를 첫 번째 줄에 출력하여라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 5점 | M ≤ 1 000 |
| #2 | 11점 | M은 짝수이며, U2i-1 = U2i, V2i-1 = V2i, C2i-1 = C2i |
| #3 | 21점 | Ci = 0 |
| #4 | 63점 | 문제의 조건 외에 주어진 제한이 없다. |
예제1
45
1244
1321
4312
4161
2425
10
2번 간선을 뒤집을 경우
(간선을 뒤집는 비용) = 1
(1번 정점에서 4번 정점까지의 최단 경로의 길이) = 6
(4번 정점에서 1번 정점까지의 최단 경로의 길이) = 3
이므로 합은 10이며 이 경우가 최소이다.
예제2
45
2144
1321
4312
4361
2425
-1