原题
题目描述 Description
麦克找了个新女朋友,玛丽卡对他非常恼火并伺机报复.
因为她和他们不住在同一个城市,因此她开始准备她的长途旅行.
在这个国家中每两个城市之间最多只有一条路相通,并且我们知道从一个城市到另一个城市路上所需花费的时间.
麦克在车中无意中听到有一条路正在维修,并且那儿正堵车,但没听清楚到底是哪一条路.无论哪一条路正在维修,从玛丽卡所在的城市都能到达麦克所在的城市.
玛丽卡将只从不堵车的路上通过,并且她将按最短路线行车.麦克希望知道在最糟糕的情况下玛丽卡到达他所在的城市需要多长时间,这样他就能保证他的女朋友离开该城市足够远.
编写程序,帮助麦克找出玛丽卡按最短路线通过不堵车道路到达他所在城市所需的最长时间(用分钟表示).
输入描述 Input Description
第一行有两个用空格隔开的数N和M,分别表示城市的数量以及城市间道路的数量.1≤N≤1000,1≤M≤N*(N-1)/2.城市用数字1至N标识,麦克在城市1中,玛丽卡在城市N中.
接下来的M行中每行包含三个用空格隔开的数A,B和V.其中1≤A,B≤N,1≤V≤1000.这些数字表示在A和城市B中间有一条双行道,并且在V分钟内是就能通过.
输出描述 Output Description
输出文件的第一行中写出用分钟表示的最长时间,在这段时间中,无论哪条路在堵车,玛丽卡应该能够到达麦克处,如果少于这个时间的话,则必定存在一条路,该条路一旦堵车,玛丽卡就不能够赶到麦克处.
样例输入 Sample Input
5 7
1 2 8
1 4 10
2 3 9
2 4 10
2 5 1
3 4 7
3 5 10
样例输出 Sample Output
27
题意
题意有点迷,一开始以为是求最长路,乱打一通spfa居然过了样例,不管三七二十一就提交,结果那段错误的代码居然还能过1个点...
于是我重新看了遍题目,原来题意是这样的:求在原图的最短路上抹去一条边(相当于那条路在堵车),然后求抹去后再求最短路时的最大值.
题解
先跑一遍spfa,求最短路并按顺序记录下从1到n的最短路中的各个节点(设节点数为k),然后循环k-1(也就是最短路的边数)遍,将每k-1条边分别进行这样的操作:a.将边权置零;b.跑一遍spfa求最短路,若最短路权值和大于answer,则answer赋值为最短路权值和;c.将边权赋值为原来的权值.
代码:
uses math;
var a,b:array[0..1000,0..1000] of longint;
var v:array[1..100000] of boolean;
var dist,q,fa,l:array[0..100000] of longint;
var n,m,i,x,y,c,now,head,tail,p,num,k,ans,numm:longint;
procedure spfa(s:longint);
var now,head,tail,i,num:longint;
begin
for i:=1 to n do dist[i]:=maxlongint;
dist[1]:=0; q[1]:=1; head:=1; tail:=1; v[1]:=true; fa[1]:=0; fa[0]:=-1;
while head<=tail do
begin
now:=q[head];
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
begin
dist[b[now,i]]:=dist[now]+a[now,b[now,i]];fa[b[now,i]]:=now;
if not v[b[now,i]] then
begin
v[b[now,i]]:=true;
inc(tail);q[tail]:=b[now,i];
end;
end;
inc(head);v[now]:=false;
end;
end;
begin
readln(n,m);
for i:=1 to m do
begin
readln(x,y,c);
inc(b[x,0]); b[x,b[x,0]]:=y; a[x,y]:=c;
inc(b[y,0]); b[y,b[y,0]]:=x; a[y,x]:=c;
end;
spfa(1);p:=n;
while fa[p]>=0 do
begin
inc(numm);l[numm]:=p;p:=fa[p];
end;p:=n;
for i:=1 to numm-1 do
begin
k:=a[l[i],l[i+1]];
a[l[i],l[i+1]]:=0;a[l[i+1],l[i]]:=0;
spfa(1);
ans:=max(ans,dist[n]);
a[l[i],l[i+1]]:=k;a[l[i+1],l[i]]:=k;
end;
writeln(ans);
end.
欢迎转载,若转载请注明出处.