#P4227. 城市

    ID: 3445 传统题 2000ms 256MiB 尝试: 53 已通过: 16 难度: 8 上传者: 标签>难度分类提高+/省选-图论Dijkstra最短路 DAG拆点支配树Kahn 算法树算法LCA树上倍增CF2500

城市

城市

题目描述

A 国有 nn 座城市。城市 ss 是首都。给定 mm 条连接不同城市的双向道路,每条道路有一个正整数长度。同一对城市可由多条道路连接。

单独封闭一条道路以后,原来能到达首都的城市中,到首都的最短路变长或变得无法到达的城市数量,就是这条道路的重要度。每条道路都在其他道路全部开放的情况下单独考察。

一个城市的重要度是与它直接相连的所有道路的重要度之和。求每座城市的重要度。

输入格式

第一行两个整数 n,mn,m,分别为城市数和道路数。

接下来 mm 行,每行三个整数 u,v,lu,v,l,表示一条连接城市 uu 和 vv、长度为 ll 的道路。

最后一行一个整数 ss,表示首都编号。城市编号为 11 至 nn。

输出格式

输出 nn 行,第 ii 行一个整数,表示城市 ii 的重要度。

样例 #1

样例输入 #1

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

样例输出 #1

2
1
0
1

数据规模与约定

1≤n≤1051\le n\le10^5,1≤m≤2×1051\le m\le2\times10^5,1≤l≤1081\le l\le10^8。