JOI20 Olympic Bus

문제

https://oj.uz/problem/view/JOI20_ho_t4

문제 보기 - Olympic Bus (JOI20_ho_t4) :: oj.uz

방향 그래프 $G$가 주어지고, 각 간선별로 가중치 $c$와 비용 $d$가 있다. 간선을 정확히 하나 선택하여 뒤집을 수 있고, 이 때 드는 비용이 $d$일 때, d+1~N까지의 최단거리 + N~1까지의 최단거리 를 최소화해야 한다. (아무 간선도 안 뒤집을 수도 있다.)

$N<=200$

$M<=50000$

풀이

각 간선을 뒤집은 후 1~N까지의 최단거리를 모두 구하고, N~1까지의 최단거리 또한 모두 구할 수 있다면 문제를 해결할 수 있다.

 

간선 ${u, v, c, d}$을 뒤집은 후 1~N까지의 최단거리를 구해보자.

뒤집은 후 1~N까지의 최단 경로는 크게 2가지의 경우로 나눌 수 있다.

 

Case 1 : 최단경로에 v->u의 간선이 포함되지 않는 경우

Case 2 : 최단경로에 v->u의 간선이 포함되는 경우

 

Case 2