#P17639. [ICPC 2019 Yinchuan R] Delivery Route
[ICPC 2019 Yinchuan R] Delivery Route
题目描述
小马是一家快递公司的老板。公司需要将包裹送达 个办公室,办公室编号从 到 。特别地,第 个办公室是这家快递公司的转运站。
这些办公室之间共有 条普通的双向道路和 条单向道路。如果快递车经过第 条道路,将会消耗 的能量。通常情况下,在一条道路上消耗的能量必须是非负的。然而,得益于实验性的充电轨道,某些单向道路上的消耗值可能为负。
除此之外,小马还获得了以下公开信息。有关部门承诺,如果存在一条从 到 的单向道路,则不可能从 返回 。
为了避免快递车在路上抛锚,小刀想要找出从转运站到这些办公室的最低能量消耗。
输入格式
第一行包含四个整数 、 和 。接下来共有 行,每行包含三个整数 和 ,描述各条道路。所给的前 条道路是普通的双向道路,后 条道路是单向道路。
输出格式
输出应包含 行,第 行表示从第 个办公室到达第 个办公室的最小能量消耗(如果可能),若无法到达第 个办公室,则输出 NO PATH。
6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10
NO PATH
NO PATH
5
0
-95
-100
提示
翻译由 DeepSeek V4 Pro 完成