#Pold1016. 算法训练 最短路

    ID: 352 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>蓝桥杯-算法训练赛制:ACM来源:蓝桥杯练习系统 ID: 15 原题链接: http://lx.lanqiao.cn/problem.page?gpid=T15最短路径队列

算法训练 最短路

算法训练 最短路

题目描述

给定一个n个顶点,m条边的有向图(其中某些边权可能为负,但保证没有负环)。请你计算从1号点到其他点的最短路(顶点从1到n编号)。

输入格式

输入描述:

第一行两个整数n, m。

接下来的m行,每行有三个整数u, v, l,表示u到v有一条长度为l的边。

输入样例: 3 3 1 2 -1 2 3 -1 3 1 2

输出格式

输出描述: 共n-1行,第i行表示1号点到i+1号点的最短路。 输出样例: -1 -2

数据范围

(原站未提供,导入后需人工补齐)

样例

参考上文 
参考上文

提示

HINT:时间限制:1.0s 内存限制:256.0MB

对于10%的数据,n = 2,m = 2。

对于30%的数据,n <= 5,m <= 10。

对于100%的数据,1 <= n <= 20000,1 <= m <= 200000,-10000 <= l <= 10000,保证从任意顶点都能到达其他所有顶点。