Submission #1195362

---

Source Code Expand

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

EPS = 1e-9

#http://www.deqnotes.net/acmicpc/2d_geometry/lines
def dot(a, b):
    return a.real * b.real + a.imag * b.imag

def cross(a, b):
    return a.real * b.imag - a.imag * b.real

def distance(a, b, c):
    if dot(b-a, c-a) <= EPS:
        return abs(c-a)
    if dot(a-b, c-b) <= EPS:
        return abs(c-b)
    return abs(cross(b-a, c-a)/(b-a))

def dijkstra(s):
    dist = z[:]
    dist[s] = 0
    heap = []
    heapq.heappush(heap, (0, s))
    
    while heap:
        dd, v = heapq.heappop(heap)
        dv = dist[v]
        if dv < dd:
            continue
        for i in path[v]:
            dvi = 1
            if dist[i] > dv + dvi:
                dist[i] = dv + dvi
                heapq.heappush(heap, (dist[i], i))
    return dist

N, M = ln()

z = [10000000] * (N + 1)

path = collections.defaultdict(list)
for i in xrange(M):
    a, b = ln()
    path[a].append(b)
    path[b].append(a)


Q = n()
VDC = []
for i in xrange(Q):
    v, d, c = ln()
    VDC.append((v, d, c))

if N > 2000 or M > 2000 or Q > 2000:
    sys.exit(0)

distance = [[]]
for i in xrange(1, N + 1):
    distance.append(dijkstra(i))

color = [0] * (N + 1)
for v, d, c in VDC:
    for i, b in enumerate(distance[v]):
        if b <= d:
            color[i] = c

for c in color[1:]:
    print c

Submission Info

Judge Result