8
4
2013
1

【BZOJ2662】【BeiJing wc2012】冻结【分层图+最短路】

类似于2763，不过层与层之间的边权要改为原边权的一半。我直接改了这个细节贴2763的代码了。

?
BZOJ 2662
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
program p2662;
    type
        bian=record
            next,point,w:longint;
        end;
        heap=record
            dis,point:longint;
        end;
    var
        p,d:array[1..200000] of longint;
        x:array[1..200000] of heap;
        b:array[1..1500000] of bian;
        ans,len,s,t,n,m,k,i,j,k1,k2,k3,maxn:longint;
        now:heap;
    procedure ade(k1,k2,k3:longint);
        begin
            inc(len);
            b[len].point:=k2;
            b[len].w:=k3;
            b[len].next:=p[k1];
            p[k1]:=len;
        end;
    procedure add(k1,k2,k3:longint);
        begin
            ade(k1,k2,k3);
            ade(k2,k1,k3);
        end;
    function minn(k1,k2:longint):longint;
        begin
            if x[k1].dis<=x[k2].dis then exit(k1) else exit(k2);
        end;
    function min(k1,k2,k3:longint):longint;
        begin
            exit(minn(k1,minn(k2,k3)));
        end;
    procedure press(k:longint);
        var
            i:longint;
            j:heap;
        begin
            i:=min(k,k*2,k*2+1);
            if i=k then exit;
            j:=x[k]; x[k]:=x[i]; x[i]:=j;
            press(i);
        end;
    procedure find(k:longint);
        var
            i:heap;
        begin
                        if k=1 then exit;
            if x[k].dis<x[k div 2].dis then begin
                i:=x[k];
                x[k]:=x[k div 2];
                x[k div 2]:=i;
                find(k div 2);
            end;
        end;
    procedure push(k:heap);
        var
            i,j:longint;
        begin
            i:=p[k.point];
            while i<>0 do begin
                j:=b[i].point;
                if k.dis+b[i].w<d[j] then begin
                    d[j]:=k.dis+b[i].w;
                    inc(len);
                    x[len].point:=j;
                    x[len].dis:=d[j];
                    find(len);
                end;
                i:=b[i].next;
            end;
        end;
    begin
        readln(n,m,k);
        len:=0;
        fillchar(p,sizeof(p),0);
        fillchar(b,sizeof(b),0);
        for i:=1 to m do begin
            readln(k1,k2,k3);
            add(k1,k2,k3);
            for j:=0 to k-1 do begin
                ade(j*n+k1,j*n+n+k2,k3 div 2);
                ade(j*n+k2,j*n+k1+n,k3 div 2);
                add(j*n+n+k1,j*n+n+k2,k3);
            end;
        end;
        fillchar(d,sizeof(d),$3f);
        fillchar(x,sizeof(x),$7f);
        maxn:=x[1].dis;
        s:=1; t:=n;
        len:=1; x[1].point:=s; d[s]:=0; x[1].dis:=0;
        while len>0 do begin
            dec(len);
            now:=x[1];
            if len>0 then begin
                x[1]:=x[len+1];
                x[len+1].dis:=maxn;
                press(1);
            end;
            push(now);
        end;
        ans:=maxlongint;
        for i:=0 to k do
            if d[i*n+t]<ans then ans:=d[i*n+t];
        writeln(ans);
    end.
Category: 分层图 | Tags:
8
4
2013
1

【BZOJ2763】【JLOI2011】飞行路线【分层图+最短路】

把原图复制K+1遍，如果原来点I，J之间有边就在第P层的I向P+1层J连一条有向边，同理，第P层的点J向P+1层I连一条有向边。以第一层S为原点做最短路，答案就是所有层T点距离的最小值。应注意SPFA会T，应该用DJ+HEAP。

?
BZOJ2763
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
program p2736;
    type
        bian=record
            next,point,w:longint;
        end;
        heap=record
            dis,point:longint;
        end;
    var
        p,d:array[1..200000] of longint;
                x:array[1..200000] of heap;
        b:array[1..3000000] of bian;
        ans,len,s,t,n,m,k,i,j,k1,k2,k3,maxn:longint;
        now:heap;
    procedure ade(k1,k2,k3:longint);
        begin
            inc(len);
            b[len].point:=k2;
            b[len].w:=k3;
            b[len].next:=p[k1];
            p[k1]:=len;
        end;
    procedure add(k1,k2,k3:longint);
        begin
            ade(k1,k2,k3);
            ade(k2,k1,k3);
        end;
    function minn(k1,k2:longint):longint;
        begin
            if x[k1].dis<=x[k2].dis then exit(k1) else exit(k2);
        end;
    function min(k1,k2,k3:longint):longint;
        begin
            exit(minn(k1,minn(k2,k3)));
        end;
    procedure press(k:longint);
        var
            i:longint;
            j:heap;
        begin
            i:=min(k,k*2,k*2+1);
            if i=k then exit;
            j:=x[k]; x[k]:=x[i]; x[i]:=j;
            press(i);
        end;
    procedure find(k:longint);
        var
            i:heap;
        begin
                        if k=1 then exit;
            if x[k].dis<x[k div 2].dis then begin
                i:=x[k];
                x[k]:=x[k div 2];
                x[k div 2]:=i;
                find(k div 2);
            end;
        end;
    procedure push(k:heap);
        var
            i,j:longint;
        begin
            i:=p[k.point];
            while i<>0 do begin
                j:=b[i].point;
                if k.dis+b[i].w<d[j] then begin
                    d[j]:=k.dis+b[i].w;
                    inc(len);
                    x[len].point:=j;
                    x[len].dis:=d[j];
                    find(len);
                end;
                i:=b[i].next;
            end;
        end;
    begin
        readln(n,m,k);
        readln(s,t);
        inc(s); inc(t);
        len:=0;
        fillchar(p,sizeof(p),0);
        fillchar(b,sizeof(b),0);
        for i:=1 to m do begin
            readln(k1,k2,k3);
            inc(k1); inc(k2);
            add(k1,k2,k3);
            for j:=0 to k-1 do begin
                ade(j*n+k1,j*n+n+k2,0);
                ade(j*n+k2,j*n+k1+n,0);
                add(j*n+n+k1,j*n+n+k2,k3);
            end;
        end;
        fillchar(d,sizeof(d),$3f);
        fillchar(x,sizeof(x),$7f);
        maxn:=x[1].dis;
        len:=1; x[1].point:=s; d[s]:=0; x[1].dis:=0;
        while len>0 do begin
            dec(len);
            now:=x[1];
            if len>0 then begin
                x[1]:=x[len+1];
                x[len+1].dis:=maxn;
                press(1);
            end;
            push(now);
        end;
        ans:=maxlongint;
        for i:=0 to k do
            if d[i*n+t]<ans then ans:=d[i*n+t];
        writeln(ans);
    end.
Category: 分层图 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com