We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I wrote my code and I passes the first test case. But all the others fail. I spent a lot of time about it and can't find out what might be the problem. Thank you for your help Here is my code :
#include <stdio.h>
#include <stdlib.h>
#define INT_MAX 1000000
int N;
void printGraph(int graph[N][N]) {
int i, j;
printf("\nGraph\n");
for (i = 0; i < N; ++i) {
for (j = 0; j < N; ++j) {
printf("%d ", graph[i][j]);
}
printf("\n");
}
}
void printTab(int distances[N], int startNode) {
int i;
for (i = 0; i < N; i++)
if (distances[i] != startNode)
if (distances[i] == INT_MAX)
printf("-1 ");
else
printf("%d ", distances[i]);
printf("\n");
}
int getMinDistance (int distances[N], int Q[N]) {
int i, min = INT_MAX, minInd;
for (i = 0; i < N; i++) {
if (!Q[i])
if (distances[i] < min)
min = distances[i], minInd = i;
}
return minInd;
}
void dijkstra(int graph[N][N], int startNode) {
int distances[N];
int Q[N];
int i, j, n;
//Initialisation
for (i = 0; i < N; i++) {
distances[i] = INT_MAX, Q[i] = 0;
}
distances[startNode] = 0;
Q[startNode] = 1;
//printTab(distances, "Distances : ");
for (n = 0; n < N; n++) {
int node = getMinDistance (distances, Q);
Q[node] = 1;
//Updating neighbourhood
for (i = 0; i < N; i++) {
//printf("%d\n", i);
if (graph[node][i]) {//If i is adjacent to the current node
//printf("\tIs adjacent\n");
if (!Q[i]) {//If it hasn't been visited
//printf("\tNot been visited\n");
if (distances[node] + graph[node][i] < distances[i]) {//Update distance if it is more than the calculated one
//printf("\tUpdate\n");
distances[i] = distances[node] + graph[node][i];
}
}
}
}
}
printTab(distances, startNode);
}
int main(int argc, char const *argv[]) {
int TT, t, M, m, i, j;
scanf ("%d", &TT);
for (t = 0; t < TT; t++) {
scanf ("%d %d", &N, &M);
int graph[N][N];
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
graph[i][j] = 0;
for (m = 0; m < M; m++) {
int x, y, r;
scanf ("%d %d %d", &x, &y, &r);
if (graph[x - 1][y - 1] == 0 || graph[x - 1][y - 1] > r)
graph[x - 1][y - 1] = graph[y - 1][x - 1] = r;
}
int startNode;
scanf ("%d", &startNode);
//printGraph(graph);
//printf("Starting node : %d\n", startNode);
dijkstra(graph, startNode - 1);
}
return 0;
}
Dijkstra: Shortest Reach 2
You are viewing a single comment's thread. Return to all comments →
I wrote my code and I passes the first test case. But all the others fail. I spent a lot of time about it and can't find out what might be the problem. Thank you for your help Here is my code :