题目描述
小 Z 需要通过一张星门网络回到终点。网络中的每条星门都有一个非负的回溯时间。
星门网络是一张含有 n 个点、m 条无向边的图,点 n 是起点,点 1 是终点。每条边 (u,v,w) 的权值为非负整数 w。
小 Z 从点 n 出发,沿边行走并最终到达点 1。路线必须满足:
- 不能连续经过同一条边,也就是不能出现 a→b→a;
- 点 1 只能在路线最后出现,并且恰好出现一次;
- 其他点可以重复经过。
设路线经过的边权之和为 W。给定目标时间 t,请输出所有合法路线中 ∣W−t∣ 的最小值。
输入格式
第一行包含三个整数 n,m,t。
接下来 m 行,每行包含三个整数 u,v,w,表示一条连接点 u 与点 v、权值为 w 的无向边。
输出格式
输出一个整数,表示答案。
样例 1 输入
4 6 10
1 4 4
2 3 1
1 3 6
2 4 3
3 4 2
1 2 5
样例 1 输出
0
样例 2 输入
5 7 13
2 3 3
1 2 1
3 4 1
2 4 2
4 5 3
1 3 2
3 5 2
样例 2 输出
1
样例 3 输入
1 0 1
样例 3 输出
1
数据范围
对于所有测试数据,保证:
- 1≤n≤2×105;
- 0≤m≤2×105;
- 0≤t≤1000;
- m×t≤7×106;
- 0≤w≤106;
- 不存在重边和自环,且点 1 与点 n 连通。
| 数据类别 |
分值 |
测试点 |
附加条件 |
| A |
5 |
1 |
所有边权均为 0 |
| B |
2 |
t=0 |
| C |
10 |
3∼4 |
n≤50,m≤100,t≤1000 |
| D |
5∼6 |
n≤200,m≤1000,t≤300 |
| E |
7∼8 |
n≤500,m≤8000,t≤100 |
| F |
15 |
9∼11 |
n≤6×104,t≤80 |
| G |
20 |
12∼15 |
n≤105,t≤50 |
| H |
25 |
16∼20 |
无附加限制 |