Tìm đường đi ngắn thứ nhì

Bài toán :

Cho đồ thị có hướng( có trọng số ) gồm n đỉnh và m cạnh ( lưu ý giữa 2 đỉnh bất kì có thể có nhiều cạnh ).

Tìm độ dài của đường đi ngắn thứ nhì từ 1-> n. 

INPUT:  SHORTEST.INP

   +  Dòng 1: Chứa 2 số n và m ( 2<=n<=20.000; 0<=m<=100.000 )
   +  M dòng tiếp theo, mỗi dòng ghi 3 số nguyên dương u, v, w tương ứng là có đường đi một chiều từ u đến v và độ dài bằng w.( 1<= w <= 100.000 ). ( Các số cách nhau ít nhất 1 dấu cách )

OUTPUT : SHORTEST.OUT

   + Chứa một số nguyên duy nhật là độ dài đường đi ngắn thứ nhì từ 1->n . Nếu không có xuất -1.

Example Input 

4 6

1 2 5

1 3 5

2 3 1

2 4 5

3 4 5

1 4 13

Example Output 

11

Example Input

3 3
1 2 1
2 3 1
1 3 2

Example Output

-1

Ở ví dụ 1 ta thấy độ dài đường đi ngắn nhất từ 1->6 là 10, độ dài đường đi ngắn nhì là 11.
Ở ví dụ 2 mọi đường đi từ 1->3 đều ngắn nhất.

Thuật Toán

Gọi :

        + d1[i] (1<=i<=n) là độ dài đường đi ngắn nhất từ 1->i ;

        + dn[i] (1<=i<=n) là độ dài đường đi ngắn nhất từ  i->n;

Hiển nhiên ta thấy độ dài đường đi ngắn nhất từ 1-> n là d1[n], vấn đề ở đây là làm sao tìm được đường đi ngắn thứ NHÌ từ 1->n. Ta làm như sau :

Ta lần lượt duyệt m cạnh, cứ mỗi cạnh (u,v,w) ( thế hiện có 1 đường đi trực tiếp từ u->v có độ dài là w )
ta xét xem cạnh này có thuộc một trong những đường đi ngắn nhất từ 1-> n hay không? Nó thỏa mãn khi và chỉ khi d1[u]+dn[v]+w=d1[n], Ngược lại nếu d1[u]+dn[v]+w>d1[n] thì cạnh đó không thuộc bất kì đường đi ngắn nhất nào từ 1-> n . Như vậy cứ mỗi cạnh khôg thỏa mãn ta cập nhật lại độ dài của đường đi ngắn thứ nhì : answer=min(answer,d1[u]+dn[v]+w). 

Lưu ý:
Ta dùng dijkstra heap để giải quyết bài này. Để tìm được đường đi ngắn nhất từ một đỉnh đến đỉnh n ta phải đảo chiều đồ thị và dijkstra từ n về 1.

Code: http://ideone.com/L2tt7n