2051 - 有负权边的最短路
题目描述
给定一个 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 号点的最短路。
样例
输入
3 3 1 2 -1 2 3 -1 3 1 2
输出
-1 -2
来源
图论 spfa
标签
