Submission #1588847

---

Source Code Expand

//
//  main.cpp
//  backToProblemSolving
//
//  Created by Khaled Abdelfattah on 6/27/17.
//  Copyright © 2017 Khaled Abdelfattah. All rights reserved.
//

#include <bits/stdc++.h>
// #include <iostream>
using namespace std;

typedef long long ll;
#define MAX 1000000000
#define BASE1 23
#define BASE2 31
#define MOD1 1000000007
#define MOD2 217645177
#define eps 1e-6

vector<pair<int, int>> adjList[100005];
int n, m, bestDist[100005];
bool visited[100005];
priority_queue< pair<int, int>, vector<pair<int, int> >, greater< pair<int, int> > > pq;
int colors[100005];
void Dijkstra (int source, int d, int c) {
    for (int i = 0; i < n; ++i)
        bestDist[i] = INT_MAX, visited[i] = 0;
    pq.push(make_pair(0, source));
    bestDist[source] = 0;
    while (!pq.empty()) {
        pair<int, int> top = pq.top();
        pq.pop();
        int dist = top.first, v = top.second, sz = (int) adjList[v].size();
        if (visited[v])
            continue;
        visited[v] = true;
        for (int i = 0; i < sz; ++i) {
            pair<int, int> current = adjList[v][i];
            int neigh = current.first, weight = current.second;
            if (!visited[neigh] && bestDist[neigh] > dist + weight) {
                bestDist[neigh] = dist + weight;
                pq.push(make_pair(bestDist[neigh], neigh));
            }
        }
    }
    for (int i = 0; i < n; i ++)
        if (bestDist[i] <= d)
            colors[i] = c;
}
int main() {
    cin >> n >> m;
    memset(colors, 0, n);
    for (int i = 0; i < m; i ++) {
        int u, v;
        cin >> u >> v;
        v--, u--;
        adjList[u].push_back(make_pair(v, 1));
        adjList[v].push_back(make_pair(u, 1));
    }
    int q;
    cin >> q;
    while (q --) {
        int s, d, c;
        cin >> s >> d >> c;
        Dijkstra(s - 1, d, c);
    }
    for (int i = 0; i < n; i ++)
        cout << colors[i] << endl;
    return 0;
}

Submission Info

Judge Result