MECUNG spoj – Mê cung
Nguồn đề bài: http://vn.spoj.com/problems/MECUNG/ 1. Đề bài MECUNG spoj Trong một lần dạo chơi công viên BeeG, Nam phát hiện một trò chơi mới : mê cung. Mê cung gồm N phòng và M hành lang nối giữa các phòng. Mỗi hành lang nối 2 phòng u và v theo được sơn màu c. Bằng hành lang này ...
Nguồn đề bài: http://vn.spoj.com/problems/MECUNG/
1. Đề bài MECUNG spoj
Trong một lần dạo chơi công viên BeeG, Nam phát hiện một trò chơi mới : mê cung. Mê cung gồm N phòng và M hành lang nối giữa các phòng. Mỗi hành lang nối 2 phòng u và v theo được sơn màu c. Bằng hành lang này người ta có thể đi từ phòng u sang phòng v và ngược lại.
Một cuộc tỉ thí sắp được tổ chức. Những người tham gia sẽ bị bịt mắt và thả xuống căn phòng số 1 bằng trực thăng. Nhiệm vụ của người chơi là đến được căn phòng số N (phòng cuối cùng). Một thiết bị theo dõi sẽ được đeo vào mỗi người, ghi lại những căn phòng và hành lang mà người đó đi qua. Người sử dụng ít hành lang nhất để đến căn phòng N sẽ thắng cuộc. Nếu có nhiều người cùng sử dụng ít hành lang nhất, người có đường đi “đẹp” sẽ thắng. Một đường đi được xem là đẹp nếu dãy màu các hành lang mà người đó sử dụng liên tiếp có thứ tự từ điển nhỏ nhất trong tất các các đường đi ngắn nhất.
Quyết tâm giành chiến thắng (vì phần thưởng cực kì hậu hĩnh), Nam thuê hẳn một máy bay trực thăng bay quay công viên BeeG và chụp hình mê cung từ phía trên. Hãy giúp Nam ghi lại đường đi lí tưởng nhất.
Chú ý : Dãy (a1, a2, a3, … , ak) có thứ tự từ điển nhỏ hơn dãy (b1, b2, b3, … ,bk) nếu tồn tại một vị trí i nhỏ nhất (1 <= i <= k) sao cho ai<>bi thì ai<bi.
Giữa hai phòng có thể có nhiều hơn một hành lang.
Input
Dòng đầu gồm 2 số N, M – số phòng và số hành lang.
M dòng sau, dòng i gồm 3 số ui vi ci thể hiện một hành lang.
Giới hạn : 2 <= N <= 100000
1 <= M <= 200000
1 <= ui , vi <= N
1 <= ci<= 109
Có 33% số test có N <= 100.
Output
Dòng đầu ghi K – độ dài đường đi ngắn nhất từ phòng 1 đến phòng N.
Dòng thứ hai ghi K số là màu của K hành lang theo thứ tự được dùng để đi từ phòng 1 đến phòng N.
Example
Input:
4 6
1 3 2
3 4 3
1 2 1
2 4 4
3 1 1
2 3 1
Output:
2
1 3
2. Hướng dẫn MECUNG spoj
Gọi d1[i] là khoảng cách ngắn nhất từ đỉnh 1 tới đỉnh i, d2[i] là khoảng cách ngắn nhất từ đỉnh n tới đỉnh i, cả hai mảng d1 và d2 đều có thể dễ dàng tính qua 2 lần BFS do đồ thị không có trọng số. Tiếp đó, tôi đẩy đỉnh 1 vào stack thứ nhất, và bắt đầu quá trình loang tìm đường đi thỏa mãn đề bài:
Giả sử đang xét tới đỉnh u trong stack thứ nhất, tôi xét các đỉnh v kề với nó, tìm các đỉnh v thỏa mãn : d1[v]+d2[v]=d1[n] (để chắc chắn nếu đi theo con đường qua v thì sẽ có con đường để tới n, xem hình ảnh bên dưới), và cạnh (u,v) có số màu là nhỏ nhất, nếu có nhiều đỉnh v thỏa mãn tôi sẽ đẩy tất cả vào đỉnh stack thứ hai. Sau khi stack thứ nhất hết phần tử, tôi đẩy toàn bộ phần tử trong stack thứ hai sang stack thứ nhất và tiếp tục quá trình loang. Nên dùng một mảng lưu kết quả, vừa loang vừa cập nhật.
Một ví dụ vì sao muốn tới v thì v phải thỏa mãn: d1[v]+d2[v]=d1[n] (thỏa mãn có con đường ngắn nhất đi qua v). Từ 1 băt buộc phải đi tiếp 2 mà không thể đi tới 3 (dù cạnh (1,3) có số màu nhỏ hơn số màu cạnh (1,2) ).
3. Code MECUNG spoj
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 | program MECUNG; const maxC=trunc(1e9); type kieu=record u,v,c: longint end; arr=array[1..100010] of longint; var e: array[1..200000] of kieu; a,h: array[1..4000010] of longint; head,queue,d,d1,kq: arr; free: array[1..100010] of boolean; n,m,l,r,k: longint; stack: array[0..1,1..100000] of longint; top: array[0..1] of longint; procedure nhap; var i: longint; begin read(n,m); for i:=1 to m do with e[i] do read(u,v,c); for i:=1 to m do with e[i] do begin inc(head[u]); inc(head[v]); end; for i:=2 to n do head[i]:=head[i-1]+head[i]; head[n+1]:=head[n]; for i:=1 to m do with e[i] do begin a[head[u]]:=v; h[head[u]]:=c; a[head[v]]:=u; h[head[v]]:=c; dec(head[u]); dec(head[v]); end; end; procedure init; var i: longint; begin l:=1; r:=0; for i:=1 to n do free[i]:=true; end; procedure push(u: longint); begin inc(r); queue[r]:=u; end; function pop: longint; begin pop:=queue[l]; inc(l); end; procedure BFS(s: longint; var d: arr); var u,v,i: longint; begin init; push(s); free[s]:=false; repeat u:=pop; for i:=head[u]+1 to head[u+1] do begin v:=a[i]; if free[v] then begin d[v]:=d[u]+1; free[v]:=false; push(v); end; end; until l>r; end; procedure main; var x,y,i,u,min,v,j,tm: longint; begin BFS(1,d); BFS(n,d1); x:=0;y:=1; top[x]:=1; stack[x][1]:=1; for i:=1 to n do free[i]:=true; free[1]:=false; repeat min:=maxC; for i := top[x] downto 1 do begin u := stack[x][i]; for j := head[u] + 1 to head[u + 1] do begin v := a[j]; if (free[v]) and (d[u] + 1 + d1[v] = d[n]) then if (h[j] < min) then min := h[j]; end; end; for i:=top[x] downto 1 do begin u:=stack[x][i]; for j:=head[u]+1 to head[u+1] do begin v:=a[j]; if free[v] and (d[u] + 1 + d1[v] = d[n]) then if h[j]=min then begin inc(top[y]); stack[y][top[y]]:=v; free[v] := false; end; end; end; inc(k); kq[k]:=min; tm:=x; x:=y; y:=tm; top[y]:=0; until k=d[n]; writeln(k); for i:=1 to k do write(kq[i],' '); end; BEGIN nhap; main; END. |
