#CW39. 星门回响(beyond)

星门回响(beyond)

题目描述

小 Z 需要通过一张星门网络回到终点。网络中的每条星门都有一个非负的回溯时间。

星门网络是一张含有 nn 个点、mm 条无向边的图,点 nn 是起点,点 11 是终点。每条边 (u,v,w)(u,v,w) 的权值为非负整数 ww。

小 Z 从点 nn 出发,沿边行走并最终到达点 11。路线必须满足:

  • 不能连续经过同一条边,也就是不能出现 a→b→aa \to b \to a;
  • 点 11 只能在路线最后出现,并且恰好出现一次;
  • 其他点可以重复经过。

设路线经过的边权之和为 WW。给定目标时间 tt,请输出所有合法路线中 ∣W−t∣|W-t| 的最小值。

输入格式

第一行包含三个整数 n,m,tn,m,t。

接下来 mm 行,每行包含三个整数 u,v,wu,v,w,表示一条连接点 uu 与点 vv、权值为 ww 的无向边。

输出格式

输出一个整数,表示答案。

样例 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×1051 \le n \le 2 \times 10^5;
  • 0≤m≤2×1050 \le m \le 2 \times 10^5;
  • 0≤t≤10000 \le t \le 1000;
  • m×t≤7×106m \times t \le 7 \times 10^6;
  • 0≤w≤1060 \le w \le 10^6;
  • 不存在重边和自环,且点 11 与点 nn 连通。
数据类别 分值 测试点 附加条件
A 5 11 所有边权均为 00
B 22 t=0t=0
C 10 3∼43\sim 4 n≤50n \le 50,m≤100m \le 100,t≤1000t \le 1000
D 5∼65\sim 6 n≤200n \le 200,m≤1000m \le 1000,t≤300t \le 300
E 7∼87\sim 8 n≤500n \le 500,m≤8000m \le 8000,t≤100t \le 100
F 15 9∼119\sim 11 n≤6×104n \le 6\times 10^4,t≤80t \le 80
G 20 12∼1512\sim 15 n≤105n \le 10^5,t≤50t \le 50
H 25 16∼2016\sim 20 无附加限制