OpenJudge

5:金企鹅的计划

总时间限制:
10000ms
单个测试点时间限制:
1000ms
内存限制:
256000kB
描述

一张图,有很多点,有很多边,我们从这张图中选取一些边(选取边需要一定代价)构成新图,构成一张新图

新图要求:

1、所有点到1号点的最短路等于原图的最短路

2、保证1的前提下使选取的总代价最小

(由于网站附件大小原因,此版本数据弱化,只有6个点)

输入
第一行 n,m表示有n个点
接下来的m行,每行a,b,s,w四个正整数,表示在原图中在a号点与b号点之间有一条线相连,s为更新的代价,w为线的长度。
输出
第一行 n个整数,每个整数之间用空格隔开,表示编号为n的点到教师机的距离。
第二行 一个整数,表示更新的最小费用,结果可能很大,需取模10^9 + 7。
若无法做到,则输出“0TZ”
样例输入
5 6
1 2 20 100
2 4 20 120
1 4 10 220
2 3 10 90
3 5 10 110
1 5 10 120
样例输出
0 100 190 220 120
50
提示
N <= 10^5 M <= 4 * 10^5 保证所有s,w的值在10^5范围内。
来源
bjx模拟
全局题号
11313
添加于
2016-09-03
提交次数
2
尝试人数
2
通过人数
1