POJ 3159
题目大意&＃xff1a;给n个小朋友们分糖果&＃xff0c;其中有m个关系a b c&＃xff0c;代表A允许B比自己最多多C个糖果&＃xff0c;求第一个小朋友到第n个小朋友的糖果数的差最大是多少&＃xff08;满足这m个条件下&＃xff09;
解&＃xff1a;题目有隐藏题意&＃xff0c;第n个小朋友&＃xff08;即班长要比1多&＃xff09;&＃xff0c;所以这些条件就是一个差分约束&＃xff0c;然后求1到n的最短路即可&＃xff08;dist[x]表示1允许x比自己多多少&＃xff0c;把关系传递&＃xff0c;显然是一个最短路模型&＃xff0c;如果存在一条1到x的路比已知短&＃xff0c;显然要更新才能满足题意。&＃xff09;&＃xff0c;初始化全部为bilibili&＃xff0c;dist[1]为0&＃xff0c;鬼畜的是即使是spfa&＃43;slf&＃43;queue也会tle&＃xff0c;但是用spfa&＃43;stack就会很快&＃xff08;我刷上第四名&＃xff09;&＃xff0c;300&＃43;ms&＃xff0c;dij&＃43;heap也要500ms。
spfa&＃43;stack 1 //poj 3159
2 const
3 maxn&＃61;31111;
4 maxm&＃61;151111;
5 bilibili&＃61;maxlongint >> 1;
6 type
7 data&＃61;record
8 cost, dest, next: longint;
9 end;
10 var
11 edge: array[1..maxm]of data;
12 q, vect, dist: array[1..maxn]of longint;
13 visit: array[1..maxn]of boolean;
14 n, m, tot, ans: longint;
15 procedure add(x, y, z: longint);
16 begin
17 inc(tot);
18 with edge[tot] do begin
19 dest :&＃61; y;
20 cost :&＃61; z;
21 next :&＃61; vect[x];
22 vect[x] :&＃61; tot;
23 end;
24 end;
25
26 procedure init;
27 var
28 i, x, y, z: longint;
29 begin
30 tot :&＃61; 0; ans :&＃61; 0;
31 fillchar(vect, sizeof(vect), 0);
32 readln(n, m);
33 for i :&＃61; 1 to m do begin
34 readln(x, y, z);
35 add(x, y, z);
36 end;
37 end;
38
39 function spfa(source: longint): longint;
40 var
41 i, u, head, tail, key: longint;
42 begin
43 fillchar(dist, sizeof(dist), 0);
44 fillchar(visit, sizeof(visit), 0);
45 tail :&＃61; 1;
46 q[tail] :&＃61; source; visit[source] :&＃61; true;
47 filldword(dist, sizeof(dist)>>2, bilibili);
48 dist[source] :&＃61; 0;
49 repeat
50 u :&＃61; q[tail];
51 dec(tail);
52 visit[u] :&＃61; false;
53 i :&＃61; vect[u];
54 while i<>0 do
55 with edge[i] do begin
56 if dist[dest]>dist[u]&＃43;cost then begin
57 dist[dest] :&＃61; dist[u] &＃43; cost;
58 if not visit[dest] then begin
59 visit[dest] :&＃61; true;
60 inc(tail);
61 q[tail] :&＃61; dest;
62 end;
63 end;
64 i :&＃61; next;
65 end;
66 until tail<&＃61;0;
67 spfa :&＃61; dist[n];
68 end;
69
70 procedure main;
71 begin
72 ans :&＃61; spfa(1);
73 end;
74
75 procedure print;
76 begin
77 writeln(ans);
78 end;
79
80 begin
81 assign(input,&＃39;1.txt&＃39;); reset(input);
82 init;
83 main;
84 print;
85 end.
dijkstra&＃43;heap 1 //poj 3159
2 const
3 maxn&＃61;31111;
4 maxm&＃61;151111;
5 bilibili&＃61;maxlongint >> 1;
6 type
7 data&＃61;record
8 cost, dest, next: longint;
9 end;
10 var
11 edge: array[1..maxm]of data;
12 heap, poss, vect, dist: array[1..maxn]of longint;
13 visit: array[1..maxn]of boolean;
14 hptot, n, m, tot, ans: longint;
15 procedure add(x, y, z: longint);
16 begin
17 inc(tot);
18 with edge[tot] do begin
19 dest :&＃61; y;
20 cost :&＃61; z;
21 next :&＃61; vect[x];
22 vect[x] :&＃61; tot;
23 end;
24 end;
25
26 procedure init;
27 var
28 i, x, y, z: longint;
29 begin
30 tot :&＃61; 0; ans :&＃61; 0;
31 fillchar(vect, sizeof(vect), 0);
32 readln(n, m);
33 for i :&＃61; 1 to m do begin
34 readln(x, y, z);
35 add(x, y, z);
36 end;
37 end;
38
39 procedure up(x: longint);
40 var
41 i, tmp: longint;
42 begin
43 i :&＃61; x;
44 tmp :&＃61; heap[x];
45 while i>1 do begin
46 if dist[tmp]
47 heap[i] :&＃61; heap[i >> 1];
48 poss[heap[i]] :&＃61; i;
49 i :&＃61; i >> 1;
50 end
51 else break;
52 end;
53 heap[i] :&＃61; tmp;
54 poss[tmp] :&＃61; i;
55 end;
56
57 procedure down(X: longint);
58 var
59 i, j, tmp: longint;
60 begin
61 i :&＃61; x;
62 tmp :&＃61; heap[x];
63 while i <<1 <&＃61; hptot do begin
64 j :&＃61; i <<1;
65 if (j&＃43;1<&＃61;hptot)and(dist[heap[j]]>dist[heap[j&＃43;1]]) then inc(j);
66 if dist[tmp]>dist[heap[j]] then begin
67 heap[i] :&＃61; heap[j];
68 poss[heap[i]] :&＃61; i;
69 i :&＃61; j;
70 end
71 else break;
72 end;
73 heap[i] :&＃61; tmp;
74 poss[tmp] :&＃61; i;
75 end;
76
77 function dijkstra(source: longint): longint;
78 var
79 i, u: longint;
80 begin
81 fillchar(poss, sizeof(poss), 0);
82 hptot :&＃61; 0; poss[source] :&＃61; -1; u :&＃61; 1;
83 filldword(dist, sizeof(dist)>>2, bilibili);
84 dist[source] :&＃61; 0;
85 repeat
86 if u&＃61;n then break;
87 i :&＃61; vect[u];
88 while i<>0 do
89 with edge[i] do begin
90 if dist[dest]>dist[u]&＃43;cost then begin
91 dist[dest] :&＃61; dist[u] &＃43; cost;
92 if poss[dest] &＃61; 0 then begin
93 inc(hptot);
94 heap[hptot] :&＃61; dest; poss[dest] :&＃61; hptot;
95 up(hptot);
96 end
97 else up(poss[dest]);
98 end;
99 i :&＃61; next;
100 end;
101 u :&＃61; heap[1];
102 poss[u] :&＃61; -1;
103 heap[1] :&＃61; heap[hptot];
104 poss[heap[1]] :&＃61; 1;
105 dec(hptot);
106 down(1);
107 until false;
108 dijkstra :&＃61; dist[n]-dist[source];
109 end;
110
111 procedure main;
112 begin
113 ans :&＃61; dijkstra(1);
114 end;
115
116 procedure print;
117 begin
118 writeln(ans);
119 end;
120
121 begin
122 assign(input,&＃39;1.txt&＃39;); reset(input);
123 init;
124 main;
125 print;
126 end.
![[大整数乘法] java代码实现](https://img1.php1.cn/3cd4a/24c6f/9f3/0133bb25da242824.jpeg)
京公网安备 11010802041100号