Description
给出一个有 个顶点 条边的有向图，对于一条边长度为len的边有两种走法。 1、如果a和b可以互达，则走过这条边的时间为len 2、如果a和b不可以互达，则走过这条边的时间为2*len 现在给出一个k，问，从顶点1到顶点n，满足第二种走法不超过k次的最短时间是多少。
第一行有3个整数n,m,k(1<=n<=100,1<=m<=10000,0<=k<=10),表示有n个顶点，m条边。 接下来有m行，每行有3个整数xi,yi,leni(1<=xi,yi<=n,1<=leni<=10000)，表示长度为leni的有向边。 注意，两个点可能有多条边连接。
Output
一行一个整数，表示最短时间。 如果没有满足题目条件的路径，则输出-1
分析
这又是一个分层图。
先用floyd处理出两个点是否互达。把不互达的两点之间的边处理一下。
设f[i,j]表示到达i点用了j次第二种走法的最短路。
如果连接x,y的一条边(边权为w)是第一种边，那它更新的是f[y,j]=f[x,j]+w
如果连接x,y的一条边(边权为w)是第二种边，那它更新的是f[y,j+1]=f[x,j]+w*2
代码
const
maxn=
110;
maxe=
12000;
type
arr=
record
x,y:longint;
w:longint;
show:boolean;
next:longint;
end;
var
n,m,nm,num:longint;
s,t:longint;
edge:
array[
0..maxe]
of arr;
ls:
array[
0..maxn]
of longint;
f:
array[
0..maxn,
0..
100]
of longint;
g:
array[
0..maxn,
0..maxn]
of boolean;
queue:
array[
0..
4000000,
1..
2]
of longint;
status:
array[
0..maxn,
0..
100]
of longint;
procedure add(x,y,w:longint);
begin
num:=num+
1;
edge[num].x:=x;
edge[num].y:=y;
edge[num].w:=w;
edge[num].next:=ls[x];
edge[num].show:=
false;
ls[x]:=num;
end;
procedure init;
var
i:longint;
x,y,w:longint;
begin
readln(n,m,nm);
num:=
0;
fillchar(g,sizeof(g),
0);
for i:=
1 to m
do
begin
readln(x,y,w);
g[x,y]:=
true;
add(x,y,w);
end;
s:=
1; t:=n;
end;
procedure floyd;
var
i,j,k:longint;
begin
for k:=
1 to n
do
for i:=
1 to n
do
for j:=
1 to n
do
if (i<>j)
and (j<>k)
and (i<>k)
then
g[i,j]:=(g[i,k]
and g[k,j])
or g[i,j];
end;
procedure spfa;
var
i,j,k:longint;
head,tail:longint;
begin
fillchar(f,sizeof(f),$
7f);
head:=
0; tail:=
1;
queue[
1][
1]:=s;
queue[
1][
2]:=
0;
f[s][
0]:=
0;
status[s][
0]:=
1;
repeat
head:=head+
1;
i:=ls[queue[head][
1]];
while i<>
0 do
begin
with edge[i]
do
begin
j:=queue[head][
2];
if not show
then
if f[x,j]+w<f[y,j]
then
begin
f[y,j]:=f[x,j]+w;
if status[y][j]=
0
then
begin
tail:=tail+
1;
queue[tail][
1]:=y;
queue[tail][
2]:=j;
status[y][j]:=
1;
end;
end;
if show
then
if j<nm
then
if f[x,j]+w<f[y,j+
1]
then
begin
f[y,j+
1]:=f[x,j]+w;
if status[y][j+
1]=
0
then
begin
tail:=tail+
1;
queue[tail][
1]:=y;
queue[tail][
2]:=j+
1;
status[y][j+
1]:=
1;
end;
end;
i:=next;
end;
end;
status[queue[head][
1]][queue[head][
2]]:=
0;
until head=tail;
end;
procedure main;
var
i,j,k:longint;
ans:longint;
begin
floyd;
for i:=
1 to n
do
begin
j:=ls[i];
while j<>
0 do
with edge[j]
do
begin
if not g[x,y]
or not g[y,x]
then
begin
edge[j].show:=
true;
edge[j].w:=edge[j].w*
2;
end;
j:=next;
end;
end;
spfa;
ans:=maxlongint;
for i:=
0 to nm
do
begin
if ans>f[t,i]
then ans:=f[t,i];
end;
if ans=
2139062143
then write(-
1)
else writeln(ans);
end;
begin
init;
main;
end.
转载请注明原文地址: https://ju.6miu.com/read-1308918.html
