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 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

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.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *