#Z. 「一本通 3.2 练习 7」道路和航线
「一本通 3.2 练习 7」道路和航线
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目描述
原题来自：USACO 2011 Jan. Gold
Farmer John 正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到 个城镇 ，编号为 到 。这些城镇之间通过 条道路（编号为 到 ）和 条航线（编号为 到 ）连接。每条道路 或者航线 连接城镇 到 ，花费为 。
对于道路，，然而航线的花费很神奇，花费 可能是负数。道路是双向的，可以从 到 ，也可以从 到 ，花费都是 。然而航线与之不同，只可以从 到 。
事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策保证：如果有一条航线可以从 到 ，那么保证不可能通过一些道路和航线从 回到 。由于 FJ 的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。他想找到从发送中心城镇 把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。
输入格式
第一行为四个空格隔开的整数：；
第二到第 行：三个空格隔开的整数（表示一条道路）： 和 ；
第 到 行：三个空格隔开的整数（表示一条航线）： 和 。
输出格式
输出 行，第 行表示到达城镇 的最小花费，如果不存在输出 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
一共六个城镇。在 和 ， 和 ， 和 之间有道路，花费分别是 。同时有三条航线：， 和 ，花费分别是 。FJ 的中心城镇在城镇 。FJ 的奶牛从 号城镇开始，可以通过道路到达 号城镇。然后他们会通过航线达到 和 号城镇。但是不可能到达 和 号城镇。
数据范围与提示
对于全部数据，$1\le T\le 2.5\times 10^4,1\le R,P\le 5\times 10^4,1\le A_i,B_i,S\le T$。保证对于所有道路，，对于所有航线，。
2024级新生ACM培训课后习题十： 图论算法
- Status
- Done
- Problem
- 48
- Open Since
- 2024-12-13 12:00
- Deadline
- 2025-9-1 23:59
- Extension
- 0 hour(s)