A70746. 有负权边的最短路
编程题
入门
知识点
题目描述
给定一个 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
3 3 1 2 -1 2 3 -1 3 1 2
输出 #1
-1 -2
说明/提示
## 思路
「有负权边的最短路」先建图再遍历或求特殊路径。
## 步骤
1. 读入点数边数并建邻接表。
2. 按题意 DFS/BFS 或求最短路、欧拉路。
3. 输出路径或距离。
「有负权边的最短路」先建图再遍历或求特殊路径。
## 步骤
1. 读入点数边数并建邻接表。
2. 按题意 DFS/BFS 或求最短路、欧拉路。
3. 输出路径或距离。