最短路 给定一个n个点, m条边的有向图, 求从点S出发, 到其它所有点的最短路径. 时间限制：2000 内存限制：65536 输入 第一行一个整数T, 表示有T组数据 对于每组测试数据, 第一行三个整数n, m, S, 表示有n个点, m条边, 起点为S. 接下来m行, 每行三个整数x, y, z, 代表从x到y有长度为z的边 点的编号从1到n T <= 10, n <= 10000, m <= 20000, |z| <= 10000. 所有数据的n之和 <= 30000, 所有数据的m之和 <= 60000. 输出 对于每组数据: 如果从S点出发可以走入负圈 (即到某些点的最短路径可以无限小), 那么输出一行Error. 否则, 输出一行用空格分隔的n个整数, 其中第i个整数表示从S点到i点的最短路长度. 如果从S点无法到达i点, 则第i个输出为”null”. 样例输入 4 5 7 1 1 2 3 2 3 4 3 4 8 1 3 9 4 5 1 1 4 5 1 5 10 4 4 1 1 2 -4 2 3 8 1 3 5 3 4 0 3 3 2 1 2 -3 2 3 -4 3 1 6 4 2 1 1 2 1 3 4 2 样例输出 0 3 7 5 6 0 -4 4 4 Error 0 1 null null
正确答案：参考程序（C++）：SPFA判负环求最短路。从S出发，若某点入队次数≥n则存在负圈输出Error。否则输出S到各点最短路，不可达输出null。样例第三组检测负环输出Error。核心：SPFA判负环。
试卷来源：202212 青少年等级考试C/C++真题八级