N개의 정점과 M개의 단방향 간선으로 이루어진 그래프가 있다.

i번 간선은 정점 U_i에서 정점 V_i로 향하며, 길이는 Ci이다.

또한, i번 간선을 뒤집는 비용은 D_i이다.

간선을 뒤집는다는 것은 정점 U_i에서 정점 V_i로 향하는 간선을 정점 V_i에서 정점 U_i로 향하는 간선으로 교체하는 것이다.

최대 한 개의 간선을 뒤집어서, (1번 정점에서 N번 정점으로 가는 최단경로의 길이) + (N번 정점에서 1번 정점으로 가는 최단경로의 길이) + (간선을 뒤집는 비용)의 최솟값을 구하여라.

복잡한 그래프 문제 timer 2s memory 512MB

복잡한 그래프 문제 2s 512MB