type    lian = ^node;
                node = record
                        st,co:longint;
                        next:lian;
end;
        rec = record
                le:longint;
                ss:ansistring;
end;
const   maxn = 100000;
        oo = maxlongint >> 1;
var     da:array[0..maxn] of lian;
        pp:array[0..maxn] of longint;
        ju:array[0..maxn] of boolean;
        dist:array[0..maxn] of rec;
        n,m,ans:longint;
        anss:ansistring;

        procedure init;
        var     x,y,c,i:longint;
                p:lian;
                kg:boolean;
        begin
                readln(n,m);
                for i:=1 to n do
                begin
                        da[i]:=nil;
                        ju[i]:=false;
                        dist[i].le:=oo;
                        dist[i].ss:='ZZZZ';
                end;
                dist[1].le:=0;  dist[1].ss:='';
                for i:=1 to m do
                begin
                        readln(x,y,c);
                        if x = y then continue;
                        p:=da[x];  kg:=true;
                        while p <> nil do
                        begin
                                if p^.st = y then
                                begin
                                        if p^.co > c then p^.co:=c;
                                        kg:=false;  break;
                                end;
                                p:=p^.next;
                        end;
                        if kg then
                        begin
                                new(p);
                                p^.st:=y;
                                p^.co:=c;
                                p^.next:=da[x];
                                da[x]:=p;
                        end;

                        p:=da[y];  kg:=true;
                        while p <> nil do
                        begin
                                if p^.st = x then
                                begin
                                        if p^.co > c then p^.co:=c;
                                        kg:=false;  break;
                                end;
                                p:=p^.next;
                        end;
                        if kg then
                        begin
                                new(p);
                                p^.st:=x;
                                p^.co:=c;
                                p^.next:=da[y];
                                da[y]:=p;
                        end;
                end;
                ans:=oo;
                anss:='ZZZZ';
        end;

        procedure work;
        var     i,head,tail,now,y,x,z:longint;
                s,s1,s2:ansistring;
                p:lian;
                kg:boolean;
        begin
                now:=1;  pp[1]:=1;  head:=1;  tail:=1;  ju[1]:=true;
                repeat
                        p:=da[now];
                        while p <> nil do
                        begin
                                y:=p^.st;  x:=dist[now].le;  z:=dist[y].le;
                                s1:=dist[now].ss;  s2:=dist[y].ss;
                                str(p^.co,s);
                                if s1 <> '' then
                                        s:=s1+' '+s+' '
                                else    s:=s+' ';
                                if x+1 < z then
                                begin
                                        dist[y].le:=x+1;
                                        dist[y].ss:=s;
                                        if not ju[y] then
                                        begin
                                                inc(tail);
                                                pp[tail]:=y;
                                                ju[y]:=true;
                                        end
                                end
                                else
                                if x+1 = z then
                                begin
                                        if s < s2 then
                                        begin
                                                dist[y].ss:=s;
                                                if not ju[y] then
                                                begin
                                                        inc(tail);
                                                        pp[tail]:=y;
                                                        ju[y]:=true;
                                                end;
                                        end;
                                end;
                                kg:=false;  z:=dist[y].le;  s2:=dist[y].ss;
                                if y = n then
                                begin
                                        if z < ans then kg:=true;
                                        if ( z = ans ) and ( s2 < anss ) then kg:=true;
                                        if kg then
                                        begin
                                                ans:=z;
                                                anss:=s2;
                                        end;
                                end;
                                p:=p^.next;
                        end;
                        inc(head);
                        ju[now]:=false;
                        now:=pp[head];
                until  head > tail;
                writeln(ans);
                writeln(anss);
        end;
begin
        init;
        work;
end.

• Re:SPFA为什么T？？？？自己测极限数据都是<1ms (18) xqjfd 2011-10-18 17:48:14