Task: | Sadonkorjuu |
Sender: | Ihminen |
Submission time: | 2022-11-13 18:38:23 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#2 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#3 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#4 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#5 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#6 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#7 | WRONG ANSWER | 0.00 s | 2 | details |
#8 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#9 | WRONG ANSWER | 0.00 s | 2 | details |
#10 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#11 | WRONG ANSWER | 0.00 s | 2 | details |
#12 | WRONG ANSWER | 0.00 s | 2 | details |
#13 | WRONG ANSWER | 0.00 s | 2 | details |
#14 | WRONG ANSWER | 0.00 s | 2 | details |
#15 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#16 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#17 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#18 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#19 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#20 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#21 | WRONG ANSWER | 0.00 s | 2 | details |
#22 | WRONG ANSWER | 0.00 s | 2 | details |
#23 | WRONG ANSWER | 0.00 s | 2 | details |
#24 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#25 | WRONG ANSWER | 0.00 s | 2 | details |
#26 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#27 | WRONG ANSWER | 0.00 s | 2 | details |
#28 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#29 | WRONG ANSWER | 0.00 s | 2 | details |
#30 | WRONG ANSWER | 0.00 s | 1, 2 | details |
#31 | WRONG ANSWER | 0.00 s | 2 | details |
Compiler report
input/code.cpp: In function 'void dijkstra(Graph*, int)': input/code.cpp:305:23: warning: '*dist[src]' may be used uninitialized [-Wmaybe-uninitialized] 305 | newMinHeapNode(src, dist[src]); | ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
Code
#include <bits/stdc++.h>// A structure to represent a// node in adjacency liststruct AdjListNode{int dest;int weight;struct AdjListNode* next;};// A structure to represent// an adjacency liststruct AdjList{// Pointer to head node of liststruct AdjListNode* head;};// A structure to represent a graph.// A graph is an array of adjacency lists.// Size of array will be V (number of// vertices in graph)struct Graph{int V;struct AdjList* array;};// A utility function to create// a new adjacency list nodestruct AdjListNode* newAdjListNode(int dest, int weight){struct AdjListNode* newNode =(struct AdjListNode*)malloc(sizeof(struct AdjListNode));newNode->dest = dest;newNode->weight = weight;newNode->next = NULL;return newNode;}// A utility function that creates// a graph of V verticesstruct Graph* createGraph(int V){struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));graph->V = V;// Create an array of adjacency lists.// Size of array will be Vgraph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));// Initialize each adjacency list// as empty by making head as NULLfor (int i = 0; i < V; ++i)graph->array[i].head = NULL;return graph;}// Adds an edge to an undirected graphvoid addEdge(struct Graph* graph, int src,int dest, int 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 beginningstruct AdjListNode* newNode =newAdjListNode(dest, weight);newNode->next = graph->array[src].head;graph->array[src].head = newNode;// Since graph is undirected,// add an edge from dest to src alsonewNode = newAdjListNode(src, weight);newNode->next = graph->array[dest].head;graph->array[dest].head = newNode;}// Structure to represent a min heap nodestruct MinHeapNode{int v;int dist;};// Structure to represent a min heapstruct MinHeap{// Number of heap nodes present currentlyint size;// Capacity of min heapint capacity;// This is needed for decreaseKey()int* pos;struct MinHeapNode** array;};// A utility function to create a// new Min Heap Nodestruct MinHeapNode* newMinHeapNode(int v,int dist){struct MinHeapNode* minHeapNode =(struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));minHeapNode->v = v;minHeapNode->dist = dist;return minHeapNode;}// A utility function to create a Min Heapstruct MinHeap* createMinHeap(int capacity){struct MinHeap* minHeap =(struct MinHeap*)malloc(sizeof(struct MinHeap));minHeap->pos = (int*)malloc(capacity * sizeof(int));minHeap->size = 0;minHeap->capacity = capacity;minHeap->array =(struct MinHeapNode**)malloc(capacity *sizeof(struct MinHeapNode*));return minHeap;}// A utility function to swap two// nodes of min heap.// Needed for min heapifyvoid swapMinHeapNode(struct MinHeapNode** a,struct MinHeapNode** b){struct MinHeapNode* t = *a;*a = *b;*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()void minHeapify(struct MinHeap* minHeap,int idx){int smallest, left, right;smallest = idx;left = 2 * idx + 1;right = 2 * idx + 2;if (left < minHeap->size &&minHeap->array[left]->dist <minHeap->array[smallest]->dist)smallest = left;if (right < minHeap->size &&minHeap->array[right]->dist <minHeap->array[smallest]->dist)smallest = right;if (smallest != idx){// The nodes to be swapped in min heapMinHeapNode* smallestNode =minHeap->array[smallest];MinHeapNode* idxNode =minHeap->array[idx];// Swap positionsminHeap->pos[smallestNode->v] = idx;minHeap->pos[idxNode->v] = smallest;// Swap nodesswapMinHeapNode(&minHeap->array[smallest],&minHeap->array[idx]);minHeapify(minHeap, smallest);}}// A utility function to check if// the given minHeap is empty or notint isEmpty(struct MinHeap* minHeap){return minHeap->size == 0;}// Standard function to extract// minimum node from heapstruct MinHeapNode* extractMin(struct MinHeap*minHeap){if (isEmpty(minHeap))return NULL;// Store the root nodestruct MinHeapNode* root =minHeap->array[0];// Replace root node with last nodestruct MinHeapNode* lastNode =minHeap->array[minHeap->size - 1];minHeap->array[0] = lastNode;// Update position of last nodeminHeap->pos[root->v] = minHeap->size - 1;minHeap->pos[lastNode->v] = 0;// Reduce heap size and heapify root--minHeap->size;minHeapify(minHeap, 0);return root;}// Function to decreasekey dist value// of a given vertex v. This function// uses pos[] of min heap to get the// current index of node in min heapvoid decreaseKey(struct MinHeap* minHeap,int v, int dist){// Get the index of v in heap arrayint i = minHeap->pos[v];// Get the node and update its dist valueminHeap->array[i]->dist = dist;// Travel up while the complete// tree is not heapified.// This is a O(Logn) loopwhile (i && minHeap->array[i]->dist <minHeap->array[(i - 1) / 2]->dist){// Swap this node with its parentminHeap->pos[minHeap->array[i]->v] =(i - 1) / 2;minHeap->pos[minHeap->array[(i - 1) / 2]->v] = i;swapMinHeapNode(&minHeap->array[i],&minHeap->array[(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 notbool isInMinHeap(struct MinHeap* minHeap, int v){if (minHeap->pos[v] < minHeap->size)return true;return false;}// A utility function used to print the solutionvoid printArr(int dist[], int n){printf("Vertex Distance from Source\n");for (int i = 0; i < n; ++i)printf("%d \t\t %d\n", i, dist[i]);}// The main function that calculates// distances of shortest paths from src to all// vertices. It is a O(ELogV) functionvoid dijkstra(struct Graph* graph, int src){// Get the number of vertices in graphint V = graph->V;// dist values used to pick// minimum weight edge in cutint dist[V];// minHeap represents set Estruct MinHeap* minHeap = createMinHeap(V);// Initialize min heap with all// vertices. dist value of all verticesfor (int v = 0; v < V; ++v){dist[v] = INT_MAX;minHeap->array[v] = newMinHeapNode(v,dist[v]);minHeap->pos[v] = v;}// Make dist value of src vertex// as 0 so that it is extracted firstminHeap->array[src] =newMinHeapNode(src, dist[src]);minHeap->pos[src] = src;dist[src] = 0;decreaseKey(minHeap, 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 (!isEmpty(minHeap)){// Extract the vertex with// minimum distance valuestruct MinHeapNode* minHeapNode =extractMin(minHeap);// Store the extracted vertex numberint u = minHeapNode->v;// Traverse through all adjacent// vertices of u (the extracted// vertex) and update// their distance valuesstruct AdjListNode* pCrawl =graph->array[u].head;while (pCrawl != NULL){int v = pCrawl->dest;// If shortest distance to v is// not finalized yet, and distance to v// through u is less than its// previously calculated distanceif (isInMinHeap(minHeap, v) &&dist[u] != INT_MAX &&pCrawl->weight + dist[u] < dist[v]){dist[v] = dist[u] + pCrawl->weight;// update distance// value in min heap alsodecreaseKey(minHeap, v, dist[v]);}pCrawl = pCrawl->next;}}// print the calculated shortest distancesprintArr(dist, V);}// Driver program to test above functionsint main(){// create the graph given in above figureint V = 9;struct Graph* graph = createGraph(V);addEdge(graph, 0, 1, 4);addEdge(graph, 0, 7, 8);addEdge(graph, 1, 2, 8);addEdge(graph, 1, 7, 11);addEdge(graph, 2, 3, 7);addEdge(graph, 2, 8, 2);addEdge(graph, 2, 5, 4);addEdge(graph, 3, 4, 9);addEdge(graph, 3, 5, 14);addEdge(graph, 4, 5, 10);addEdge(graph, 5, 6, 2);addEdge(graph, 6, 7, 1);addEdge(graph, 6, 8, 6);addEdge(graph, 7, 8, 7);dijkstra(graph, 0);return 0;}
Test details
Test 1
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1 0 |
correct output |
---|
0 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 2
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
5 0 0 0 0 0 1 2 1 2 3 2 3 4 3 ... |
correct output |
---|
0 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 3
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
4 1 0 1 1 1 2 10 2 3 20 2 4 30 |
correct output |
---|
60 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 4
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
5 0 1 1 1 0 1 2 10 2 3 20 3 4 30 ... |
correct output |
---|
80 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 5
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
5 0 1 0 1 1 1 2 1 2 3 5 3 4 3 ... |
correct output |
---|
6 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 6
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
5506363 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 7
Group: 2
Verdict: WRONG ANSWER
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1795118520 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 8
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1000 0 0 1 0 1 1 0 1 0 1 1 0 0 0 1 ... |
correct output |
---|
293576 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 9
Group: 2
Verdict: WRONG ANSWER
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
816932444 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 10
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
3089 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 11
Group: 2
Verdict: WRONG ANSWER
input |
---|
200000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
40839 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 12
Group: 2
Verdict: WRONG ANSWER
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
5683983203973 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 13
Group: 2
Verdict: WRONG ANSWER
input |
---|
200000 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 ... |
correct output |
---|
58572993 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 14
Group: 2
Verdict: WRONG ANSWER
input |
---|
200000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
32755 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 15
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
126238345 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 16
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1000 0 0 0 1 0 1 1 1 0 0 1 0 1 1 0 ... |
correct output |
---|
278678 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 17
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1000 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 ... |
correct output |
---|
34929 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 18
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1543963 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 19
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
39606 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 20
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1000 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 ... |
correct output |
---|
321598 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 21
Group: 2
Verdict: WRONG ANSWER
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
978670626 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 22
Group: 2
Verdict: WRONG ANSWER
input |
---|
200000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
375218 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 23
Group: 2
Verdict: WRONG ANSWER
input |
---|
200000 1 1 1 1 0 0 0 0 0 1 0 1 0 1 1 ... |
correct output |
---|
60422556 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 24
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
291990 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 25
Group: 2
Verdict: WRONG ANSWER
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
59607954 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 26
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
990 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 27
Group: 2
Verdict: WRONG ANSWER
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
199982 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 28
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
7987 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 29
Group: 2
Verdict: WRONG ANSWER
input |
---|
200000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
3137875 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 30
Group: 1, 2
Verdict: WRONG ANSWER
input |
---|
1000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
4657693 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |
Test 31
Group: 2
Verdict: WRONG ANSWER
input |
---|
200000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1652889357 |
user output |
---|
Vertex Distance from Source 0 0 1 4 2 12 3 19 ... Truncated |