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

Read More

TUTORIAL CODEFORCES ROUND 314

Link contest : http://codeforces.com/contest/567.

Problem A :  http://codeforces.com/contest/567/problem/A

1.giải thích đề

Có n thành phố nằm trên trục tọa độ Ox theo thứ tự tăng dần  (không có thành phố nào cùng nằm trên một tọa độ)
Tại mỗi thành phố cần tìm ra khoảng cách ngắn nhất và lớn nhất đến một thành phố khác nào đó

2.Thuật toán

Vì tọa độ các thành phố được sắp xếp theo thứ tự tăng dần nên tại mỗi thành phố i, ta dễ dàng xác định được :
  + 2 thành phố có khoảng cách ngắn nhất đến nó là i-1(nếu i>1) va i+1(nếu i<n). tìm min 2 thằng đó
  + 2 thành phố có khoảng cách xa nhất đến nó là 1 và n. tìm max 2 thằng đó

3.Solution
http://ideone.com/BOx2Hb

Problem B : http://codeforces.com/contest/567/problem/B

1.giải thích đề

Có một cái phòng, trước cửa phòng có một máy hệ thống(có camera) ghi lại những sự kiện người nào đó đi ra và đi vào.Tất cả mọi người được đánh số từ 1->1000000.

Read More