Description

　　给出一个有 个顶点 条边的有向图，对于一条边长度为len的边有两种走法。
　　1、如果a和b可以互达，则走过这条边的时间为len
　　2、如果a和b不可以互达，则走过这条边的时间为2*len
　　现在给出一个k，问，从顶点1到顶点n，满足第二种走法不超过k次的最短时间是多少。

Input

　　第一行有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

Sample Input

7 7 3

1 2 2

1 3 2

2 4 3

4 7 5

3 5 4

5 6 1

6 4 2

Sample Output

20

题目解释

这道题我在做的时候被坑了一下，就是在:

这段描述上，我理解成了如果a可以到b，那么长度为len，而如果在这时b不可以到a，那么可以使长度为2*len后，也可以通过。
而实际上，题目的意思是有n个点，m条有向边，其中任意两个点a，b，它们间的距离分别为$len_a$和$len_b$，如果a可以到b，b也可以到a，那么它们之间的距离不变，但如果a可以到b，b却不可以到a，那么a到b的距离为$2*len_{a}$，反之相同。
那么在走这种不可互达的边小于等于k次时，最少的距离是多少？

题解

先用Floyd求出点与点之间的最短路，再用分层SPFA求出走不可互达边的最小距离。
因为对于这种算法我也很难再多加解释，所以不理解的还是看下面吧。

---

varx,y,s,n,m,k,i,j,o,ans:longint;a,b:array[0..1000,0..1000] of longint;f:array[1..1000,0..100] of longint;d:array[1..1000,1..2] of longint;bz:array[1..1000,0..100] of boolean;
procedure spfa;
varl,r,i,j,k,o:longint;
beginfillchar(d,sizeof(d),0);fillchar(bz,sizeof(bz),false);fillchar(f,sizeof(f),$7f div 3);f[1,0]:=0;bz[1,0]:=true;d[1,1]:=1;d[1,2]:=0;l:=1;r:=1;while l<=r dobegink:=d[l,1];j:=d[l,2];for i:=1 to n do if a[k,i]<>a[0,0] thenbeginif b[i,k]=1 then o:=0 else o:=1;if f[i,j+o]>a[k,i]+f[k,j] thenbeginf[i,j+o]:=a[k,i]+f[k,j];if not bz[i,j+o] thenbegininc(r);d[r,1]:=i;d[r,2]:=j+o;bz[i,j+o]:=true;end;end;end;bz[k,j]:=false;inc(l);end;
end;
beginreadln(n,m,k);fillchar(a,sizeof(a),$7f div 3);for i:=1 to n dofor j:=1 to n do b[i,j]:=2;for i:=1 to m dobeginreadln(x,y,s);b[x,y]:=1;if a[x,y]>s then a[x,y]:=s;end;for i:=1 to n dofor j:=1 to n dofor o:=1 to n doif (j<>o) and (i<>o) and (i<>j) thenif (b[i,o]=1) and (b[o,j]=1) then b[i,j]:=1;for i:=1 to n dofor j:=1 to n doif a[i,j]<>a[0,0] then a[i,j]:=a[i,j]*b[j,i];spfa;ans:=a[0,0];for i:=0 to k do if ans>f[n,i] then ans:=f[n,i];if ans=a[0,0] then writeln(-1) else writeln(ans);
end.