Submission #1195525

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>

using namespace std;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

int main(){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<vector<int>> conn(n);
	for(int i = 0; i < m; ++i){
		int a, b;
		cin >> a >> b;
		--a; --b;
		conn[a].push_back(b);
		conn[b].push_back(a);
	}
	int q;
	cin >> q;
	vector<vector<pii>> table(n, vector<pii>(11, pii(0, -1)));
	priority_queue<tiii> pq;
	for(int i = 0; i < q; ++i){
		int r, d, c;
		cin >> r >> d >> c;
		--r;
		table[r][d] = pii(c, i);
		pq.emplace(i, r, d);
	}
	while(!pq.empty()){
		const int i = get<0>(pq.top());
		const int u = get<1>(pq.top());
		const int d = get<2>(pq.top());
		pq.pop();
		if(d == 0 || table[u][d].second != i){ continue; }
		for(const auto v : conn[u]){
			if(i > table[v][d - 1].second){
				table[v][d - 1] = pii(table[u][d].first, i);
				pq.emplace(i, v, d - 1);
			}
		}
	}
	for(int v = 0; v < n; ++v){
		int max_c = 0, max_i = -1;
		for(const auto p : table[v]){
			if(p.second > max_i){
				max_c = p.first;
				max_i = p.second;
			}
		}
		cout << max_c << '\n';
	}
	return 0;
}

Submission Info

Judge Result