Skip to content

1020: 跑路

题目

题目描述

某管理员被评测姬玩坏了,现在她要带着她的评测姬跑路。

考虑有一个$n$个点$m$条边组成的图。

现在我们要从$1$号点到$n$号点,但是不能同时通过从$1$到$n$任意一条最短路上的连续$k$条边(无向边必须按照最短路上的方向),求满足条件的最短路径。如果不存在(无论如何无法在要求下抵达),输出$-1$。

输入格式

第一行三个整数$n,m,k$,表示节点数,边数,阈值(含义同问题描述)。

接下来$m$行每行四个整数$u,v,l,t$,表示从$u$到$v$有一条长度为$l$,类型为$t$的边。其中$t=0$表示这是一条有向边,$t=1$表示这是一条无向边。

输出格式

一行一个整数$ans$,表示所求答案。

样例输入

Input 1

5 5 2 1 2 21502 1 1 3 27247 1 3 4 32212 1 2 5 14273 1 5 3 20973 1

Input 2

10 10 5 1 2 21 0 2 3 87 1 1 4 13 1 2 5 1 0 2 6 13 1 1 7 36 1 5 8 89 1 3 9 33 0 3 10 52 1 6 10 96 0

样例输出

Output 1

48220

Output 2

130

数据范围

对于$30\%$的数据,$n\le 100,m\le 10'000,k\le 5$;

对于另外$20\%$的数据,图上的边均为无向边;

对于$100\%$的数据,$n\le 100'000,m\le 500'000,k\le 10$。

保证对于所有边,$0<l\le 1'000'000'000$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!