28111번 - 평범한 그래프와 이상한 쿼리

이 문제는 단순한 그래프와 이상한 쿼리 문제와 $w_i$의 제한을 제외하고 같은 문제이다.

정점 $N$개, 간선 $M$개로 구성된 평범한 무향 가중치 그래프 $G$가 주어진다. 각 정점은 $1$번부터 $N$번까지의 번호로 표현되며, 각 간선의 가중치는 양의 정수로 주어진다. 이 때, 다음과 같은 쿼리가 $Q$개 주어진다.

• a b k: $a$번 정점에서 시작하여 $b$번 정점에서 끝나는 경로 중 길이가 $k$의 배수인 것이 존재한다면 Yes를, 그렇지 않다면 No를 출력한다.

이 때, 경로에는 같은 정점 혹은 같은 간선이 여러 번 포함되어도 된다. 또한, 경로의 길이란 경로에 포함된 간선의 길이의 합으로 정의된다. 만약, 같은 간선이 경로에 여러 번 포함될 경우에는 경로의 길이에 간선의 가중치가 해당 간선을 지난 횟수만큼 더해진다. 주어지는 쿼리를 올바르게 처리해 보자.

첫 번째 줄에 정점의 수 $N$, 간선의 수 $M$, 쿼리의 수 $Q$가 공백으로 구분되어 주어진다. ($2\le N\le 100\ 000; 0\leq M\leq 200\, 000; 1 \leq Q \leq 100\ 000$)

두 번째 줄부터 $M$개의 줄에 걸쳐 각 간선의 정보를 나타내는 $3$개의 정수 $u_i, v_i, w_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 간선이 가중치 $w_i$를 가지며 $u_i$와 $v_i$를 잇는 간선이라는 뜻이다. 각 정점 쌍을 잇는 간선은 최대 $1$개임이 보장된다. ($1\leq u_i,v_i\leq N; u_i\neq v_i; 1\leq w_i\leq 10^9$)

$M+2$ 번째 줄부터 $Q$개의 줄에 걸쳐 각 쿼리가 a b k의 형태로 주어진다. ($1\leq a,b\leq N; a\neq b; 1\leq k\leq 10^9$)

주어지는 수는 모두 정수이다.

각 쿼리마다 $a$번 정점에서 시작하여 $b$번 정점에서 끝나는 길이가 $k$의 배수인 경로가 존재하면 Yes, 아니면 No를 한 줄에 하나씩 순서대로 출력한다.