Submission #1495342

---

Source Code Expand

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

long long int power(long long int x, long long int n, long long int M) {
	long long int tmp = 1;

	if (n > 0) {
		tmp = power(x, n / 2, M);
		if (n % 2 == 0) tmp = (tmp*tmp) % M;
		else tmp = (((tmp*tmp) % M)*x) % M;
	}
	return tmp;
}

long long int N, M, K, Q, W, H, L, R;
long long int ans;



int main() {
	ios::sync_with_stdio(false);
	cin >> N >> M;
	list<int>edge[100001];
	for (int i = 0; i < M; i++) {
		cin >> L >> R;
		edge[L].push_back(R);
		edge[R].push_back(L);
	}
	cin >> Q;
	vector<vector<int>>num(N + 1, vector<int>(11, -1));
	int a[100001];
	int b[100001];
	int c[100001];
	for (int i = 0; i < Q; i++) {
		cin >> a[i] >> b[i] >> c[i];
	}
	for(int i=Q-1;i>=0;i--){
		queue<pair<int, int>>QQ;
		QQ.push({ a[i],b[i] });
		while (!QQ.empty()) {
			int cc = QQ.front().second;
			int cn= QQ.front().first;
			QQ.pop();
			if (num[cn][cc] >= 0)continue;
			for (int j = 0; j <= cc; j++) {
				if (num[cn][j] == -1) {
					num[cn][j] = c[i];
				}
			}
			for (auto j : edge[cn]) {
				QQ.push({ j,cc - 1 });
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		if (num[i][0] >= 0)cout << num[i][0] << endl;
		else cout << "0\n";
	}
	return 0;
}

Submission Info

Judge Result