G. 【入门】有负权边的最短路

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

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

第一行两个整数 $n, m$

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

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

-1
-2

对于10%的数据， $n$ = 2， $m$ = 2。
对于30%的数据， $n \leqslant 5，m \leqslant 10$
对于100%的数据，$1 \leqslant n \leqslant 20000，1 \leqslant m \leqslant 200000，-10000 \leqslant l \leqslant 10000$，保证从任意顶点都能到达其他所有顶点。

牛客网