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

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

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


问题 3002. -- 最短路

3002: 最短路

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

题目描述

给出一张有向有负权无负环图,求1到每个点的最短路。

注:本题卡堆优化dijkstra/堆优化spfa/dfs-spfa

珍爱生命,远离乱搞算法

输入

第一行两个整数n,m

接下来m行,每行三个整数x,y,z,表示有一条从x到y长度为z的边

输出

共一行,为空格隔开的n个数字,表示1到1,2,...,n的最短路长度。数据保证答案、输入数据正权边之和、负权边之和不超过int的范围,如果不存在1到k的路径则输出INF

样例输入

3 1
1 2 1

样例输出

0 1 INF 

提示

n<=60,m<=90

标签

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