6499: 【模板】Bellman-Ford
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:20
Solved:12
Description
传说在某个地区有 个城市,编号分别为 ,城市之间共有 条交通路线。
而 仔仔 是一家公司的打工仔,公司的总公司设在 市,公司的业务范围覆盖了全部的 个城市。
因为公司的安排,苦逼的 仔仔 经常要去各个城市出差,而且差旅费还不报销!
为了能精打细算地省钱,仔仔 统计了各个城市之前交通费分别是多少,大多都是要花钱的路线,但是由于 仔仔 有一些内部渠道,在走某些路线的时候甚至能赚一些钱。
于是 仔仔 想知道从 市出发前往各个城市的最少花费是多少。但是可选的交通路线太多了,价格也各不相同,他希望编程大神的你能帮忙计算一下。
Input
第一行两个整数 ,分别表示城市数量和交通路线的数量
接下来 行,每行 个整数 ,表示该路线从 市出发到 市,需要花费 元。
注意: 当 为负数的时候表示走这条路线反而可以赚钱。
接下来 行,每行 个整数 ,表示该路线从 市出发到 市,需要花费 元。
注意: 当 为负数的时候表示走这条路线反而可以赚钱。
Output
共一行 个整数,分别表示从 市出发到 市的最少的花费,如果不能到达,输出 no
Sample Input Copy
7 7
4 6 3
5 6 4
5 4 -2
3 4 2
3 2 5
1 5 8
1 3 3
Sample Output Copy
0 8 3 5 8 8 no
HINT
数据范围:
数据保证不存在花费为负数的环路。
数据保证不存在花费为负数的环路。