- 1 uses math;
- 2
- var a, b: array[0..1000, 0..1000] of longint;
- 3
- var v: array[1..100000] of boolean;
- 4
- var dist, q, fa, l: array[0..100000] of longint; //数组开大了才能AC,不然会在最后一个点莫名RE
- 5
- var n, m, i, x, y, c, now, head, tail, p, num, k, ans, numm: longint;
- 6 procedure spfa(s: longint);
- 7
- var now, head, tail, i, num: longint;
- 8 begin 9
- for i: =1 to n do dist[i] : =maxlongint;
- 10 dist[1] : =0;
- q[1] : =1;
- head: =1;
- tail: =1;
- v[1] : =true;
- fa[1] : =0;
- fa[0] : =-1; //fa[i]表示最短路中i的前驱节点(前一个节点)
- 11
- while head <= tail do //队列搞宽搜
- 12 begin 13 now: =q[head];
- 14
- for i: =1 to b[now, 0] do
- if (dist[b[now, i]] > dist[now] + a[now, b[now, i]]) and(a[now, b[now, i]] > 0) then //一定要加上a数组的限制条件
- 15 begin 16 dist[b[now, i]] : =dist[now] + a[now, b[now, i]];
- fa[b[now, i]] : =now;
- 17
- if not v[b[now, i]] then 18 begin 19 v[b[now, i]] : =true;
- 20 inc(tail);
- q[tail] : =b[now, i];
- 21 end;
- 22 end;
- 23 inc(head);
- v[now] : =false;
- 24 end;
- 25 end;
- 26 begin 27 readln(n, m);
- 28
- for i: =1 to m do 29 begin 30 readln(x, y, c);
- 31 inc(b[x, 0]);
- b[x, b[x, 0]] : =y;
- a[x, y] : =c;
- 32 inc(b[y, 0]);
- b[y, b[y, 0]] : =x;
- a[y, x] : =c; //建无向图
- 33 end;
- 34 spfa(1);
- p: =n; //先求一波最短路
- 35
- while fa[p] >= 0 do 36 begin 37 inc(numm);
- l[numm] : =p;
- p: =fa[p]; //l数组记录最短路上的各个节点
- 38 end;
- p: =n;
- 39
- for i: =1 to numm - 1 do 40 begin 41 k: =a[l[i], l[i + 1]];
- 42 a[l[i], l[i + 1]] : =0;
- a[l[i + 1], l[i]] : =0; //抹边
- 43 spfa(1); //再求一波最短路
- 44 ans: =max(ans, dist[n]); //更新答案
- 45 a[l[i], l[i + 1]] : =k;
- a[l[i + 1], l[i]] : =k; //加回权值
- 46 end;
- 47 writeln(ans);
- 48 end.
来源: