結果

問題 No.1600 Many Shortest Path Problems
コンテスト
ユーザー e869120
提出日時 2021-05-07 14:46:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,948 bytes
コンパイル時間 739 ms
コンパイル使用メモリ 78,160 KB
実行使用メモリ 19,200 KB
最終ジャッジ日時 2024-07-01 14:17:00
合計ジャッジ時間 14,757 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 19 WA * 5 RE * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

class UnionFind {
public:
	vector<int> par;

	void init(int sz) {
		par.resize(sz);
		for (int i = 0; i < sz; i++) par[i] = -1;
	}
	int root(int pos) {
		if (par[pos] == -1) return pos;
		par[pos] = root(par[pos]);
		return par[pos];
	}
	void unite(int u, int v) {
		u = root(u); v = root(v);
		if (u == v) return;
		par[u] = v;
	}
	bool same(int u, int v) {
		if (root(u) == root(v)) return true;
		return false;
	}
};

// 入力ほか
long long mod = 1000000007;
long long N, M, Q;
long long A[1 << 18], B[1 << 18], C[1 << 18];
long long X[1 << 18], Y[1 << 18], Z[1 << 18];
long long dist[1 << 18];
vector<pair<int, long long>> G[1 << 18];

void dfs(int pos, int pre, long long dep) {
	dist[pos] = dep;
	for (int i = 0; i < G[pos].size(); i++) {
		int to = G[pos][i].first;
		long long cost = G[pos][i].second;
		if (to == pre) continue;
		dfs(to, pos, (dep + cost) % mod);
	}
}

long long solve(int x, int y, int z) {
	for (int i = 1; i <= N; i++) G[i].clear();
	for (int i = 1; i <= N; i++) dist[i] = (1 << 30);

	UnionFind UF;
	UF.init(N + 2);
	for (int i = 1; i <= Q; i++) {
		if (i == z) continue;
		if (UF.same(A[i], B[i]) == false) {
			UF.unite(A[i], B[i]);
			G[A[i]].push_back(make_pair(B[i], C[i]));
			G[B[i]].push_back(make_pair(A[i], C[i]));
		}
	}

	dfs(x, -1, 0);
	if (dist[y] == (1 << 30)) return -1;
	return dist[y];
}

int main() {
	// Step #1. 入力
	scanf("%lld%lld", &N, &M);
	for (int i = 1; i <= M; i++) scanf("%lld%lld", &A[i], &B[i]);
	scanf("%lld", &Q);
	for (int i = 1; i <= Q; i++) scanf("%lld%lld%lld", &X[i], &Y[i], &Z[i]);
	C[1] = 2LL;
	for (int i = 2; i <= M; i++) C[i] = (2LL * C[i - 1]) % mod;
	assert(N <= 2000 && M <= 2000);

	// Step #2. クエリに答える
	for (int i = 1; i <= Q; i++) {
		long long ans = solve(X[i], Y[i], Z[i]);
		printf("%lld\n", ans);
	}
	return 0;
}
0