Got it!!!

How to consider duplicate edges. We need to take edge with minimum distance into account right?

what exactly do you mean by duplicate edges

what exactly do you mean by duplicate edges

thanks bro :)

Whoever thought of this gotcha is made of pure evil. It also really doesn't help that I completely missed the text in bold "If there are edges between the same pair of nodes with different weights, they are to be considered as is, like multiple edges."

FUCKING EVIL.

Yes, I skim problem descriptions. Still evil.

So glad I checked the discussion this time, I thought I was going crazy.

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;
}

We just have to use the edge with least weight right?

thanks a lot :D that was the mistake i was making..

I did learn a lot from this problem. Following are the things people using java need to care of:

1. Use fast I/O
2. Prefer adjacency list to matrix
3. For the last test case - I filtered data while taking input itself, removed all parallel edges keeping just the shortest weight edges.

the definition clearly says undirected, and a well defined graph can have at most 1 undirected edge between any 2 nodes, 2 if they are directed. something is fishy :)

Really, I was scratching my head due to this for 5 hours

and if you code in Java use buffered reader

Thanks for this! I was about to gouge my eyes out looking at TC#7.

LOL =))))))

Thanks a lot for telling this!! I wasn't able to find out where I went wrong,lol.

I made your mistake. Took me days to figure it out. Just came here to leave a comment similar to yours; should've come earlier.

It cost me 10 fucking days.....

thank you!

Thank you! I was staring at my code for so long trying to figure out what the error was. Your comment helped me find it!

Thanks Man!! really wasn't able to figure out the problem

I was stuck for like an hour stuck because of this!

Thanks man, I was stuck due to this, for like 10-15 min.

import java.io.*;
import java.util.*;

public class Solution 
{
    static double PI = 3.1415926535;
    private static long mod = 1000000007;
    static PrintWriter out = new PrintWriter(System.out);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st = new StringTokenizer("");
    public static void main(String[] args)  throws IOException
    {
        int t=Integer.parseInt(br.readLine());
        while(t-->0)
        {
            st=new StringTokenizer(br.readLine());
            int n=Integer.parseInt(st.nextToken());
            int m=Integer.parseInt(st.nextToken());
            int arr[][]=new int[n][n];
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    arr[i][j]=Integer.MAX_VALUE;
                }
            }
            for(int i=0;i<m;i++)
            {
                st=new StringTokenizer(br.readLine());
                int u=Integer.parseInt(st.nextToken())-1;
                int v=Integer.parseInt(st.nextToken())-1;
                int w=Integer.parseInt(st.nextToken());
                if(arr[u][v]>w || arr[v][u]>w)
                {
                    arr[u][v]=w;
                    arr[v][u]=w;
                }
            }
            int src=Integer.parseInt(br.readLine())-1;
            int dist[]=new int[n];
            boolean sptset[]=new boolean[n];
            for(int i=0;i<n;i++)
            {
                sptset[i]=false;
                dist[i]=Integer.MAX_VALUE;
            }
            dist[src]=0;
            for(int c=0;c<n-1;c++)
            {
                int u=findMin(dist,sptset);
                sptset[u]=true;
                //System.out.println("u "+u+" "+"dist "+dist[u]);
                for(int i=0;i<n;i++)
                {
                    if(!sptset[i] && arr[u][i]!=Integer.MAX_VALUE && 
                       dist[u]!=Integer.MAX_VALUE && dist[u]+arr[u][i]<dist[i])
                    {
                        dist[i]=dist[u]+arr[u][i];
                    }
                }
            }
            for(int i=0;i<n;i++)
            {
                if(i!=src)
                {
                    if(dist[i]==Integer.MAX_VALUE) System.out.print("-1 ");
                    else System.out.print(dist[i]+" ");
                }
            }
            System.out.println();
        }
    }
    public static int findMin(int dist[],boolean sptset[])
    {
        int min=Integer.MAX_VALUE;
        int index=-1;
        for(int i=0;i<dist.length;i++)
        {
            if(!sptset[i] && dist[i]<=min)
            {
                min=dist[i];
                index=i;
            }
        }
        return index;
    }
}

Assuming your algorithm is generaly optimal, its probably Java's IO

You might want to use java fast IO from Quora or this one from stack overflow

Same here, after reading your post, I tested and realized my reading time is 8.2s, and processing time is 0.6s! Just curious, if you use priority queue, how do you do "decrease-key" ? I thought we need to implement our own indexed-minheap? Thank you!

The problem setter is cheater.

Test case #7 has input file of 35MB

Building adjacency matrix first and converting it to adjacency list can be significantly faster than directly building lists/sets of edges belonging to vertices. That's because of stupid pattern in test data that turns this exercise into optimization task. Maybe you can even skip those fast scanners avoiding java.util.Scanner.

Same problem: Timeout for TestCase #7. I used map(int, sys.stdin.readline().split(' ')) instead of map(int, raw_input().split(' ')) and it worked! Thanks a lot!

Thank you! I forgot about that!

I would also add, when you're performing the check if a shorter distance has been found (distance(u) + length(u,v)), ignore the check if the distance to your vertex (distance(u)) is the max value. Otherwise you might have an overflow error like I did.

It happened to me, too. I switched from cin/cout stream I/O to C-style scanf/printf and passed.

Same thing happens in Java 7 & 8 for me. I submitted accepted answers by other people as my answer, TC7 timeout as well.

Thanks for you comments!

My solution passed the test case 7 now after I made the following one line patch!

//cin >> u >> v >> d;

scanf("%d %d %d", &u, &v, &d);

:~/language/c++$ time cat ~/Downloads/dij_input07.txt | 999 > 999.txt

real 0m2.005s user 0m1.984s sys 0m0.044s

:~/language/c++$ time cat ~/Downloads/dij_input07.txt | 99 > 99.txt

real 0m0.881s user 0m0.876s sys 0m0.036s

Thanks! Parsing the vertices was causing mine to time out.

Using C#, I used the following method to quickly convert a string into int.

public static int ConvertToInt(string s) {
  int y = 0;
  foreach (char c in s) {
    y = y * 10 + (c - '0');
  }
  return y;
}

this helped me pass test case 7 - due to time out. used the custom string to int parser which got it over the speed hump in test 7

Try sys.stdin.readline() instead of input().

For me, changing the way to read the input (either input() or sys.stdin.readline()) did not prevent the timeout. I had to use a priority queue to perform the step "find node with the least distance" of Dijkstra's algorithm.

same problem, my output includes newlines and -1. are you using javascript?

I have the same issue in bash. I tried very different inputs and all of them seems to generate the correct output, with the new line between each test case... the -1 for unreachable nodes... nothing mentioned in the description about what to be returned if two different paths with the same length are found in the graphs.