一个含有 n 个结点 m 条边的无向有权图，判断每个结点是否一定在从 1 到 n 的最短路径上
3183: 关键结点
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $5$ | 正确数量 | $0$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 |
Description
Input
第一行输入一个整数 T，代表有 T 组测试数据 对于每一组测试数据，第一行有 2 个整数 n,m，接下来m−1行每行有3个整数xi,yi, wi，表示x和y之间有一条权值为wi的边
Output
对于每组测试数据，在一行中输出 n 个整数，第 i 个整数代表 i 号结点的关键性
0 代表该结点不可能出现在从 1 到 n 的最短路径上
1 代表该结点出现在所有从 1 到 n 的最短路径上
2 代表该结点出现在部分从 1 到 n 的最短路径上
1 ≤ T ≤ 1000
2 ≤ n ≤ 1000
n − 1 ≤ m ≤ min(n × (n − 1) / 2, 2⋅105)
1≤wi ≤10^8
∑n ≤ 2⋅10^5
∑m ≤ 2⋅10^5
保证无重边无自环且连通
输出时每行末尾的多余空格，不影响答案正确性
Sample Input复制
2
6 7
1 2 1
2 3 1
2 4 1
2 5 2
3 5 1
4 5 2
5 6 1
4 6
1 2 1
1 3 1
1 4 2
2 3 1
2 4 1
3 4 1
Sample Output复制
1 1 2 0 1 1
1 2 2 1
提示
样例解释：
推荐代码 查看3183 所有题解 上传题解视频得图灵币
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$ $ms] | |||
| 内存最少[$ $KB] | |||
| 第一AC | |||
| 第一挑战 | 淡意的温柔 | 605875 | 2020-07-06 14:45:02 |
赛题来源/所属竞赛 ICPC NEAU Programming Contest 2020 N/A
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|