做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2551. -- 地铁费用

2551: 地铁费用

时间限制: 1 Sec  内存限制: 128 MB
提交: 226  解决: 70
[上一题][提交][讨论版][状态][下一题]

题目描述

公元8888年,大部分地球居民都迁移至S星球。在S星球,有n个城市,m段高速地铁。地铁是按路程来收费的,举个例子,城市1到城市n的路程是99公里,那么收取99个S币。如果城市1到城市n有多条路径可以选择,按最短那条路来收费。
现在,有一个好人在城市x坐地铁,请问从城市x到其他城市,分别需要花费多少个S币?
(注意:不能到达的城市,不需要任何费用,即费用为0;两个城市之间可以有多条直接相连的地铁,且费用不一样。)

输入

第一行:3个整数n、m、x
接下来m行,每行3个整数a、b、c,表示城市a到城市b的路程是c公里

输出

n行,第i行表示到城市i的费用。

样例输入

6 5 1
1 2 5
2 3 8
1 4 2
4 5 2
5 3 2

样例输出

0
5
6
2
4
0

提示

5 <= n <= 10000
10 <= m <= 100000
1 <= a、b <= n
1 <= c <= 100
60%的数据:n <= 5000
80%的数据:n <= 8000

标签

[上一题][提交][讨论版][状态][下一题]