Submission #34226

#TimeUsernameProblemLanguageResultExecution timeMemory
34226leejseoJakarta Skyscrapers (APIO15_skyscraper)Pypy 2
10 / 100
1065 ms256 KiB
from heapq import * MAX_INT = int(2E9) class Edge(object): def __init__(self, to, weight): self.to = to self.weight = weight class Node(object): def __init__(self, u, dist): self.u = u self.dist = dist def __cmp__(self, other): return cmp(self.dist, other.dist) def dijkstra(V, start, adj_list): Q = [] dist = [MAX_INT for i in range(V)] dist[start] = 0 heappush(Q, Node(start, 0)) while Q: u = Q[0].u dist_u = Q[0].dist heappop(Q) if dist[u] < dist_u : continue for i in range(len(adj_list[u])): v = adj_list[u][i].to dist_v = dist_u + adj_list[u][i].weight if dist_v < dist[v]: dist[v] = dist_v heappush(Q, Node(v, dist_v)) return dist N, M = map(int, raw_input().split()) doge = [None]*M for i in range(M): doge[i] = map(int, raw_input().split()) adj_list = [ [] for i in range(M) ] for i in range(M): for j in range(M): if i != j and ((doge[i][0] - doge[j][0])%doge[i][1] == 0 ): adj_list[i].append(Edge(j, abs(doge[i][0] - doge[j][0])/doge[i][1])) ans = dijkstra(M, 0, adj_list) if ans[1] == MAX_INT: print -1 else: print ans[1]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...