← 返回题单

题单练习图论

← 上一题下一题 →

A70746 | $有负权边的最短路$

来源编程题

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

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

输入格式

第一行两个整数 n,m 。 接下来的 m 行，每行有三个整数 u, v, l ，表示 u 到 v 有一条长度为 l 的边。 数据范围 对于 10\% 的数据，n = 2，m = 2。 对于 30\% 的数据，n \le 5，m \le 10。 对于 100\% 的数据，1 \le n \le 20000，1 \le m \le 200000，-10000 \le l \le 10000，保证从任意顶点都能到达其他所有顶点。

输出格式

共 n-1 行，第 i 行表示 1 号点到 i+1 号点的最短路。

输入输出样例

输入 #1

输出 #1

-1
-2

C++ 编辑器

输入

输出