Task: | Sadonkorjuu |
Sender: | hoodarm |
Submission time: | 2022-11-09 20:05:00 +0200 |
Language: | Python3 (CPython3) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | TIME LIMIT EXCEEDED | 0 |
#2 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.02 s | 1, 2 | details |
#2 | ACCEPTED | 0.02 s | 1, 2 | details |
#3 | ACCEPTED | 0.02 s | 1, 2 | details |
#4 | ACCEPTED | 0.02 s | 1, 2 | details |
#5 | ACCEPTED | 0.02 s | 1, 2 | details |
#6 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#7 | TIME LIMIT EXCEEDED | -- | 2 | details |
#8 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#9 | TIME LIMIT EXCEEDED | -- | 2 | details |
#10 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#11 | TIME LIMIT EXCEEDED | -- | 2 | details |
#12 | TIME LIMIT EXCEEDED | -- | 2 | details |
#13 | TIME LIMIT EXCEEDED | -- | 2 | details |
#14 | TIME LIMIT EXCEEDED | -- | 2 | details |
#15 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#16 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#17 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#18 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#19 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#20 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#21 | TIME LIMIT EXCEEDED | -- | 2 | details |
#22 | TIME LIMIT EXCEEDED | -- | 2 | details |
#23 | TIME LIMIT EXCEEDED | -- | 2 | details |
#24 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#25 | TIME LIMIT EXCEEDED | -- | 2 | details |
#26 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#27 | TIME LIMIT EXCEEDED | -- | 2 | details |
#28 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#29 | TIME LIMIT EXCEEDED | -- | 2 | details |
#30 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#31 | TIME LIMIT EXCEEDED | -- | 2 | details |
Code
# A Python program for Dijkstra's shortest# path algorithm for adjacency# list representation of graphfrom collections import defaultdictimport mathimport sysimport timeclass Heap():def __init__(self):self.array = []self.size = 0self.pos = []def newMinHeapNode(self, v, dist):minHeapNode = [v, dist]return minHeapNode# A utility function to swap two nodes# of min heap. Needed for min heapifydef swapMinHeapNode(self, a, b):t = self.array[a]self.array[a] = self.array[b]self.array[b] = t# A standard function to heapify at given idx# This function also updates position of nodes# when they are swapped.Position is needed# for decreaseKey()def minHeapify(self, idx):smallest = idxleft = 2*idx + 1right = 2*idx + 2if (left < self.size andself.array[left][1]< self.array[smallest][1]):smallest = leftif (right < self.size andself.array[right][1]< self.array[smallest][1]):smallest = right# The nodes to be swapped in min# heap if idx is not smallestif smallest != idx:# Swap positionsself.pos[self.array[smallest][0]] = idxself.pos[self.array[idx][0]] = smallest# Swap nodesself.swapMinHeapNode(smallest, idx)self.minHeapify(smallest)# Standard function to extract minimum# node from heapdef extractMin(self):# Return NULL wif heap is emptyif self.isEmpty() == True:return# Store the root noderoot = self.array[0]# Replace root node with last nodelastNode = self.array[self.size - 1]self.array[0] = lastNode# Update position of last nodeself.pos[lastNode[0]] = 0self.pos[root[0]] = self.size - 1# Reduce heap size and heapify rootself.size -= 1self.minHeapify(0)return rootdef isEmpty(self):return True if self.size == 0 else Falsedef decreaseKey(self, v, dist):# Get the index of v in heap arrayi = self.pos[v]# Get the node and update its dist valueself.array[i][1] = dist# Travel up while the complete tree is# not heapified. This is a O(Logn) loopwhile (i > 0 and self.array[i][1] <self.array[(i - 1) // 2][1]):# Swap this node with its parentself.pos[ self.array[i][0] ] = (i-1)//2self.pos[ self.array[(i-1)//2][0] ] = iself.swapMinHeapNode(i, (i - 1)//2 )# move to parent indexi = (i - 1) // 2;# A utility function to check if a given# vertex 'v' is in min heap or notdef isInMinHeap(self, v):if self.pos[v] < self.size:return Truereturn Falseclass Graph():def __init__(self, V):self.V = Vself.graph = defaultdict(list)# Adds an edge to an undirected graphdef addEdge(self, src, dest, weight):# Add an edge from src to dest. A new node# is added to the adjacency list of src. The# node is added at the beginning. The first# element of the node has the destination# and the second elements has the weightnewNode = [dest, weight]self.graph[src].insert(0, newNode)# Since graph is undirected, add an edge# from dest to src alsonewNode = [src, weight]self.graph[dest].insert(0, newNode)# The main function that calculates distances# of shortest paths from src to all vertices.# It is a O(ELogV) functiondef dijkstra(self, src):V = self.V # Get the number of vertices in graphdist = [] # dist values used to pick minimum# weight edge in cut# minHeap represents set EminHeap = Heap()# Initialize min heap with all vertices.# dist value of all verticesfor v in range(V):dist.append(1e7)minHeap.array.append( minHeap.newMinHeapNode(v, dist[v]))minHeap.pos.append(v)# Make dist value of src vertex as 0 so# that it is extracted firstminHeap.pos[src] = srcdist[src] = 0minHeap.decreaseKey(src, dist[src])# Initially size of min heap is equal to VminHeap.size = V;# In the following loop,# min heap contains all nodes# whose shortest distance is not yet finalized.while minHeap.isEmpty() == False:# Extract the vertex# with minimum distance valuenewHeapNode = minHeap.extractMin()u = newHeapNode[0]# Traverse through all adjacent vertices of# u (the extracted vertex) and update their# distance valuesfor pCrawl in self.graph[u]:v = pCrawl[0]# If shortest distance to v is not finalized# yet, and distance to v through u is less# than its previously calculated distanceif (minHeap.isInMinHeap(v) anddist[u] != 1e7 and \pCrawl[1] + dist[u] < dist[v]):dist[v] = pCrawl[1] + dist[u]# update distance value# in min heap alsominHeap.decreaseKey(v, dist[v])return dist# Driver program to test the above functionsnoOfCities = int(input())numbers = list(map(int, input().split()))graph = Graph(noOfCities)for i in range(1,noOfCities):information = list(map(int, input().split()))graph.addEdge(information[0]-1, information[1]-1, information[2])totalshortest = 0for t in range(0,noOfCities):shortest = math.infanswer = graph.dijkstra(t)for i in answer:if ((numbers[answer.index(i)]==0) and i<shortest):shortest = itotalshortest=totalshortest+shortestprint (totalshortest)
Test details
Test 1
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1 0 |
correct output |
---|
0 |
user output |
---|
0 |
Test 2
Group: 1, 2
Verdict: ACCEPTED
input |
---|
5 0 0 0 0 0 1 2 1 2 3 2 3 4 3 ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 3
Group: 1, 2
Verdict: ACCEPTED
input |
---|
4 1 0 1 1 1 2 10 2 3 20 2 4 30 |
correct output |
---|
60 |
user output |
---|
60 |
Test 4
Group: 1, 2
Verdict: ACCEPTED
input |
---|
5 0 1 1 1 0 1 2 10 2 3 20 3 4 30 ... |
correct output |
---|
80 |
user output |
---|
80 |
Test 5
Group: 1, 2
Verdict: ACCEPTED
input |
---|
5 0 1 0 1 1 1 2 1 2 3 5 3 4 3 ... |
correct output |
---|
6 |
user output |
---|
6 |
Test 6
Group: 1, 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
5506363 |
user output |
---|
(empty) |
Test 7
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1795118520 |
user output |
---|
(empty) |
Test 8
Group: 1, 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 0 0 1 0 1 1 0 1 0 1 1 0 0 0 1 ... |
correct output |
---|
293576 |
user output |
---|
(empty) |
Test 9
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
816932444 |
user output |
---|
(empty) |
Test 10
Group: 1, 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
3089 |
user output |
---|
(empty) |
Test 11
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
40839 |
user output |
---|
(empty) |
Test 12
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
5683983203973 |
user output |
---|
(empty) |
Test 13
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 ... |
correct output |
---|
58572993 |
user output |
---|
(empty) |
Test 14
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
32755 |
user output |
---|
(empty) |
Test 15
Group: 1, 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
126238345 |
user output |
---|
(empty) |
Test 16
Group: 1, 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 0 0 0 1 0 1 1 1 0 0 1 0 1 1 0 ... |
correct output |
---|
278678 |
user output |
---|
(empty) |
Test 17
Group: 1, 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 ... |
correct output |
---|
34929 |
user output |
---|
(empty) |
Test 18
Group: 1, 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1543963 |
user output |
---|
(empty) |
Test 19
Group: 1, 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
39606 |
user output |
---|
(empty) |
Test 20
Group: 1, 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 ... |
correct output |
---|
321598 |
user output |
---|
(empty) |
Test 21
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
978670626 |
user output |
---|
(empty) |
Test 22
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
375218 |
user output |
---|
(empty) |
Test 23
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 1 1 1 1 0 0 0 0 0 1 0 1 0 1 1 ... |
correct output |
---|
60422556 |
user output |
---|
(empty) |
Test 24
Group: 1, 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
291990 |
user output |
---|
(empty) |
Test 25
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
59607954 |
user output |
---|
(empty) |
Test 26
Group: 1, 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
990 |
user output |
---|
(empty) |
Test 27
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
199982 |
user output |
---|
(empty) |
Test 28
Group: 1, 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
7987 |
user output |
---|
(empty) |
Test 29
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
3137875 |
user output |
---|
(empty) |
Test 30
Group: 1, 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
4657693 |
user output |
---|
(empty) |
Test 31
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1652889357 |
user output |
---|
(empty) |