Dotcpp  >  编程题库  >  蓝桥杯2023年第十四届省赛真题-独一无二
题目 3186:

蓝桥杯2023年第十四届省赛真题-独一无二

时间限制: 3s 内存限制: 192MB 提交: 111 解决: 1

题目描述

有一个包含 n 个点,m 条边的无向图,第 i 条边的边权为 ci,没有重边和自环。设 si 表示从结点 1 出发到达结点 i 的最短路的不同路径数 ( i ∈ [1, n] ), 显然可以通过删除若干条边使得 si = 1,也就是有且仅有一条从 1 到 i 的最短路,且保持最短路的路径长度不变,对于每个 i ,求出删除边数的最小值。

输入格式

输入的第一行包含两个正整数 n, m。 

接下来 m 行,每行包含三个正整数 ui , vi , ci 表示第 i 条边连接的两个点的编号和边权。 

输出格式

输出 n 行,第 i 行包含一个正整数表示对于结点 i ,删除边数的最小值, 如果 1 和 i 不连通,输出 −1 。 

样例输入

4 4
1 2 1
1 3 2
2 4 2
3 4 1

样例输出

0
0
0
1

提示

在给定的图中,只有 s4 一开始为 2,因为有两条最短路:1 → 2 → 4, 1 → 3 → 4,任意删掉一条边后,就可以只剩一条最短路。 

对于 30% 的评测用例,n ≤ 1000; 对于所有评测用例,n ≤ 105 ,0 ≤ m ≤ min{ n(n−1)/2 , 106 } ,1 ≤ ui , vi ≤ n , 1 ≤ ci ≤ 10 。

标签