#SFCR1B. 「SFCOI-1」行走

    ID: 276 Type: Default 8000ms 256MiB Tried: 71 Accepted: 8 Difficulty: 7 Uploaded By: Tags>搜索广度优先搜索图论强连通分量拓扑排序

「SFCOI-1」行走

题目背景

小 L 喜欢在图上行走,尤其喜欢走出一条最长路。

题目描述

他给你一张 nn 个节点 mm 条边的有向且边带权的图和一个整数 ss,请你 1tn\forall 1 \leq t \leq n,求出 sts \to t按位或最长路

输入格式

第一行,三个整数 n,m,sn, m, s

接下来 mm 行,每行三个整数 u,v,wu, v, w,表示一条有向边。

输出格式

一行,nn 个整数,当不存在一条从 ssii 的路径,第 ii 个整数为 1-1;否则,第 ii 个整数为 sis \to i 的按位或最长路。

10 10 1
1 2 1
2 3 2
2 4 3
4 5 4
4 6 5
5 6 6
6 7 7
7 5 8
7 8 9
9 10 10
0 1 3 3 15 15 15 15 -1 -1

样例 #1 解释

该样例对应的图如上。以下为构造从 11 到每个点的按位或最长路的方案之一:

  • 1111
  • 22121 \to 2
  • 331231 \to 2 \to 3
  • 441241 \to 2 \to 4
  • 5512456751 \to 2 \to 4 \to 5 \to 6 \to 7 \to 5
  • 6612467561 \to 2 \to 4 \to 6 \to 7 \to 5 \to 6
  • 77124671 \to 2 \to 4 \to 6 \to 7
  • 881246781 \to 2 \to 4 \to 6 \to 7 \to 8
  • 99:不存在一条从 1199 的有向路径。
  • 1010:不存在一条从 111010 的有向路径。

数据范围

本题开启捆绑测试。

Subtask nn mm 分值
11 1n5×1031 \leq n \leq 5 \times 10^3 0m3×1040 \leq m \leq 3 \times 10^4 20pts20 \operatorname{pts}
22 0m1050 \leq m \leq 10^5
33 无特殊限制 30pts30 \operatorname{pts}
44 无特殊限制

对于 100%100\% 的数据,1n2×1041 \leq n \leq 2 \times 10^40m3×1050 \leq m \leq 3 \times 10^51s,u,vn1 \leq s, u, v \leq n0w<2130 \leq w < 2^{13}