POJ2253 (忘记初始化，然后怀孕了……浪费了2个小时啊尼玛)；
题目大意：在坐标系上给出n个点（2<=n<=200），每两个点直接可互相到达，所有从1到2的可能的路径中，最长的那条路径最短为多少
解：二分即可，二分枚举上界，再用dij求路径是否可能。
View Code
1 const
2 maxn=200;
3 bilibili=maxlongint>>1;
4 type
5 point=record
6 x, y: longint;
7 end;
8
9 graph=record
10 next, dest: longint;
11 cost: double;
12 end;
13 var
14 edge: array[1..maxn*maxn]of graph;
15 w: array[1..maxn*maxn]of longint;
16 a: array[1..maxn]of point;
17 vect, heap, poss: array[1..maxn]of longint;
18 dist: array[1..maxn]of double;
19 s, n, tot, hptot: longint;
20 key, ans: double;
21 procedure add(x, y: longint;z: double);
22 begin
23 inc(tot);
24 with edge[tot] do
25 begin
26 dest := y;
27 cost := z;
28 next := vect[x];
29 vect[x] := tot;
30 end;
31 end;
32
33 procedure qsort(b, e: longint);
34 var
35 i, j, k: longint;
36 x: double;
37 begin
38 i := b;
39 j := e;
40 x := edge[w[(i+j)>>1]].cost;
41 repeat
42 while edge[w[i]].cost<x do inc(i);
43 while edge[w[j]].cost>x do dec(j);
44 if i<=j then
45 begin
46 k := w[i];
47 w[i] := w[j];
48 w[j] := k;
49 inc(i);
50 dec(j);
51 end;
52 until i>j;
53 if j>b then qsort(b, j);
54 if i<e then qsort(i, e);
55 end;
56
57 procedure init;
58 var
59 i, j, x, y: longint;
60 aa, bb, tmp : double;
61 begin
62 readln(n);
63 if n=0 then
64 begin
65 close(input);
66 close(output);
67 halt;
68 end;
69 for i := 1 to n do
70 with a[i] do
71 readln(x, y);
72
73 filldword(dist, sizeof(dist)>>2, bilibili);
74 fillchar(poss, sizeof(poss), 0);
75 fillchar(vect, sizeof(vect), 0);
76 tot := 0;
77 hptot := 0;
78 ans := maxlongint;
79
80 for i := 1 to n-1 do
81 for j := i+1 to n do
82 begin
83 aa := (a[i].x-a[j].x)*(a[i].x-a[j].x);
84 bb := (a[i].y-a[j].y)*(a[i].y-a[j].y);
85 tmp := (aa+bb);
86 tmp := sqrt(tmp);
87 add(i, j, tmp);
88 add(j, i, tmp);
89 end;
90 for i := 1 to tot do w[i] := i;
91 qsort(1, tot);
92 end;
93
94 procedure print;
95 begin
96 write('Scenario #');
97 writeln(s);
98 write('Frog Distance = ');
99 writeln(ans:0:3);
100 writeln;
101 end;
102
103 procedure up(x: longint);
104 var
105 i, tmp: longint;
106 begin
107 i := x;
108 tmp := heap[x];
109 while i>1 do
110 begin
111 if dist[tmp]<dist[heap[i >> 1]] then
112 begin
113 heap[i] := heap[i >> 1];
114 poss[heap[i]] := i;
115 i := i >> 1;
116 end
117 else break;
118 end;
119 heap[i] := tmp;
120 poss[tmp] := i;
121 end;
122
123 procedure down(x: longint);
124 var
125 i, j, tmp: longint;
126 begin
127 i := x;
128 tmp := heap[x];
129 while i << 1<=hptot do
130 begin
131 j := i << 1;
132 if (j+1<=hptot)and(dist[heap[j]]>dist[heap[j+1]]) then inc(j);
133 if dist[tmp]>dist[heap[j]] then
134 begin
135 heap[i] := heap[j];
136 poss[heap[i]] := i;
137 i := j;
138 end
139 else break;
140 end;
141 heap[i] := tmp;
142 poss[tmp] := i;
143 end;
144
145 procedure dijkstra(b, e: longint);
146 var
147 i, u: longint;
148 begin
149 hptot := 1;
150 heap[1] := b;
151 poss[b] := 1;
152 dist[b] := 0;
153
154 repeat
155 u := heap[1];
156 if u=e then
157 begin
158 exit;
159 end;
160 heap[1] := heap[hptot];
161 poss[heap[1]] := 1;
162 dec(hptot);
163 down(1);
164 i := vect[u];
165 while i<>0 do
166 with edge[i] do
167 begin
168 if cost<=key then
169 begin
170 if dist[u] + cost < dist[dest] then
171 begin
172 dist[dest] := dist[u] + cost;
173 if poss[dest] = 0 then
174 begin
175 inc(hptot);
176 poss[dest] := hptot;
177 heap[hptot] := dest;
178 up(hptot);
179 end
180 else
181 up(poss[dest]);
182 end;
183 end;
184 i := next;
185 end;
186 until hptot<1;
187 end;
188
189
190
191 procedure main;
192 var
193 i, l, r, mid: longint;
194 begin
195 s := 0;
196 while true do
197 begin
198 inc(s);
199 init;
200 readln;
201 l := 1;
202 r := tot;
203 while l<=r do
204 begin
205 mid := (l+r)>>1;
206 key := edge[w[mid]].cost;
207 for i := 1 to n do dist[i] := bilibili;
208 fillchar(poss, sizeof(poss), 0);
209 dijkstra(1, 2);
210 if dist[2]<>bilibili then
211 begin
212 ans := key;
213 r := mid-1;
214 end
215 else
216 l := mid+1;
217 end;
218
219 print;
220 end;
221
222 end;
223
224 begin
225 //assign(input,'aaa.in'); reset(input);
226
227 main;
228
229 //close(input);
230 end.
对拍
1 var
2 f: array[1..10, 1..10]of boolean;
3 n, x, y, i: longint;
4 begin
5
6 randomize;
7 assign(output,'aaa.in'); rewrite(output);
8 n := random(6)+1;
9 writeln(n);
10 fillchar(f, sizeof(f), 0);
11 for i := 1 to n do
12 begin
13 repeat
14 x := random(10)+1;
15 y := random(10)+1;
16 until not f[x, y];
17 writeln(x, ' ', y);
18 end;
19 writeln;
20 writeln(0);
21 close(output);
22 end.