题目名称 | 3067. [CH 6703]北大ACM队的远足 |
---|---|
输入输出 | pku_acm.in/out |
难度等级 | ★★☆ |
时间限制 | 1000 ms (1 s) |
内存限制 | 256 MiB |
测试数据 | 5 |
题目来源 | syzhaoss 于2018-12-02加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:0, 提交:0, 通过率:0% | |||
关于 北大ACM队的远足 的近10条评论(全部评论) |
---|
给定一张 N 个点 M 条边的有向无环图,点的编号从 1 到 N,每条边都有一个长度。
给定一个起点 S 和一个终点 T。
若从 S 到 T 的每条路径都经过某条边,则称这条边是有向图的必经边或桥。
北大 ACM 队要从 S 点到 T 点。
他们在路上可以搭乘两次车。
每次可以从任意位置(甚至是一条边上的任意位置)上车,从任意位置下车,但连续乘坐的长度不能超过 q 米。
除去这两次乘车外,剩下的路段步行。
定义从 S 到 T 的路径的危险程度等于步行经过的桥上路段的长度之和。
求从 S 到 T 的最小危险程度是多少。
第一行包含整数 L,表示共有 L 组测试数据。
每组测试数据,第一行包含五个整数 N,M,S,T,q。
接下来 M 行,每行包含三个整数 u,v,w,表示点 u 到点 v 存在一条边,长度为 w。
每组数据输出一个结果,每个结果占一行。
若没有从 S 到 T 的路径,则输出 -1。
1 8 9 1 7 7 1 5 1 1 2 10 2 3 9 5 3 2 3 6 8 5 4 3 6 7 6 6 7 7 7 8 5
1
$1\leq L\leq 5,1\leq N\leq 10^5,1\leq M\leq 2\times 10^5,1\leq S,T\leq N,S\neq T,1\leq q\leq 10^9,1\leq w\leq 1000$