소셜 네트워크

소셜 네트워크를 연구할 때, 우리는 특정 사회 현상을 설명하기 위해 그래프 이론을 자주 사용한다.

이와 관련된 문제를 살펴보자. 한 사회 집단에 n명의 사람이 있다. 사람들 사이에는 다양한 수준의 관계가 있다. 우리는 이 관계망을 n개의 노드를 가진 무향 그래프로 나타낸다. 서로 다른 두 사람이 친밀하다면, 그래프에서 그에 대응하는 노드 사이에 무향 간선이 존재한다. 또한 간선에는 양의 가중치 c가 있으며, c가 작을수록 두 사람의 관계가 가깝다.

우리는 두 사람 s와 t에 대응하는 노드 사이의 최단 경로를 이용해 두 사람의 관계 친밀도를 측정할 수 있다. 최단 경로 위의 다른 노드들은 s와 t의 관계에 어느 정도 이익을 주며, 이 노드들은 s와 t의 관계에 대해 일정한 중요도를 가진다. 노드 v를 지나는 최단 경로를 분석하면, 전체 소셜 네트워크에 대한 v의 중요도를 측정할 수 있다.

노드 A와 B 사이에 여러 개의 최단 경로가 있을 수 있으므로, 중요도의 정의를 다음과 같이 수정한다.

C``s,t를 노드 s와 t 사이의 최단 경로의 수, C``s,t (v)를 노드 s와 t 사이의 최단 경로 중 v를 지나는 것의 수라고 하자. 소셜 네트워크에 대한 노드 v의 중요도는 다음과 같이 정의된다.

$I(v) = \sum\_{s \neq v, t \neq v}{\frac{C\_{s, t}(v)}{C\_{s, t}}}$

I(v)와 C``s,t (v)가 항상 정의되도록, 우리는 연결된 무향 그래프로 나타낼 수 있는 소셜 네트워크만 다룬다. 또한, 임의의 두 노드 사이에는 항상 유한한 길이의 최단 경로가 존재한다.

소셜 네트워크를 나타내는 이러한 가중치 무향 그래프가 주어졌을 때, 각 노드의 중요도를 계산하시오.

입력의 첫째 줄에는 소셜 네트워크의 노드 수와 무향 간선 수를 나타내는 두 정수 n과 m이 주어진다. 그래프의 노드는 1부터 n까지 연속적으로 번호가 매겨진다.

다음 m개의 줄에는 각각 노드 a와 b를 연결하는 무향 간선과 그 가중치 c를 나타내는 세 정수 a, b, c가 주어진다. 임의의 두 노드 사이에는 무향 간선이 최대 하나만 존재하며, 그래프 내에 루프(간선의 양 끝이 같은 노드에 있는 경우)는 발생하지 않는다.

n개의 줄을 출력하며, 각 줄에는 소수점 이하 3자리까지 정확한 하나의 실수를 출력한다. i번째 줄은 소셜 네트워크에 대한 노드 i의 중요도를 나타낸다. 출력한 수와 정답의 절대 오차가 0.001을 초과하지 않으면 정답으로 인정된다.

50%의 테스트 케이스: n ≤ 10, m ≤ 45
100%의 테스트 케이스: n ≤ 100, m ≤ 4500, 그리고 임의의 간선의 가중치 c는 1 ≤ c ≤ 1000을 만족하는 양의 정수이다.
데이터는 연결된 무향 그래프로 구성되며, 임의의 두 노드 사이의 최단 경로의 수는 1010을 초과하지 않음이 보장된다.