# Dijkstra: Shortest Reach 2

# Dijkstra: Shortest Reach 2

devneal + 21 comments Please make sure you guys are accounting for duplicate edges... don't make my mistake.

abhisheknovice + 1 comment Got it!!!

rsaxena_007 + 1 comment pls send me the code

karthikpriyatham + 2 comments [deleted]robbyoconnor + 0 comments [deleted]robbyoconnor + 6 comments I wish people wouldn't post solutions...

Also adjacency matrices are the least efficient way to represent graphs...use an adjacency list.

karthikpriyatham + 1 comment [deleted]robbyoconnor + 1 comment By all means, give them the worst way to do it. Teach them the WRONG way...WTG!

karthikpriyatham + 0 comments Kid. Cool !!!!!.. Deleted

rgevorky + 2 comments Well, doesn't it depend on whether the graph is dense or sparse? If we are working with a tree, for instance, adjacency lists are certainly appropriate. But if we have a graph with |E| >> |V|, it makes sense to use an adjacency matrix.

robbyoconnor + 0 comments In this case, adjacency lists are the way to do it. If you look at the complexities -- adjacency matrices almost always hit worst case...not to mention a shitton of wasted space.

robbyoconnor + 0 comments For some of the smaller cases that they will give, No. It's bad performance. You don't want an adjacency matrix unless you know the input size in advance

kiner_shah + 0 comments Worked adjacency list! :-)

Phibonacci + 0 comments It depends on what you're using them for. You have to decide what is more important... speed or memory.

emarsc + 0 comments Similarly, hiking boots are always more efficient than sneakers....

arjun_tomar + 0 comments its ok ...but here nodes<=3000 then using adjacency matrix and simple naive searching for min weight node gives the time complexity O(nodes^2) which means max to max 9000000 iterations and this should work absolutely fine(<=1second).

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

felds + 0 comments I think that's a way to do it. In this problem, the longest edge will never be used. (I didn't complete this problem yet, though. Take this with a grain of salt.)

kondalarao + 0 comments yes

robbyoconnor + 0 comments The way you do it -- is you track what you've seen -- a simple list will do...some of them edges in the order of >41,000 -- so if you have to check >10,000 edges more than once-- it will take >10s to do so and will timeout -- so filter what you have seen

mahanteshambi + 0 comments If there is a duplicate edge then store the edge which has least weight value in the matrix/ adjacency list.

karthikpriyatham + 0 comments [deleted]Dante_vergil + 0 comments what exactly do you mean by duplicate edges

Dante_vergil + 1 comment what exactly do you mean by duplicate edges

robbyoconnor + 1 comment [deleted]robbyoconnor + 0 comments [deleted]

anonymouse_pal + 0 comments thanks bro :)

tangx246 + 1 comment 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."

robbyoconnor + 0 comments [deleted]

roufamatic + 0 comments FUCKING EVIL.

Yes, I skim problem descriptions. Still evil.

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

koreissm + 2 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 :

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

pgmreddy + 0 comments using priority_queue can help, take the least one first from neighbourhood

psharma10 + 0 comments vector shortestReach(int n, vector> edges, int s) {

`vector<pair<int,int>>adj[n+1]; for(int i = 0;i<edges.size();i++) { int x = edges[i][0]; int y = edges[i][1]; int z = edges[i][2]; adj[x].push_back(make_pair(y,z)); adj[y].push_back(make_pair(x,z)); } priority_queue< pair<int,int> , vector<pair<int,int>> , greater<pair<int,int>> >pq; vector<long long int>dist( n+1 , INT_MAX); bool visited[n+1]; for(int i = 0;i<=n;i++) { visited[i] = false; } dist[s] = 0; pq.push(make_pair(0,s)); visited[s] = true; while(!pq.empty()) { int u = pq.top().second; pq.pop(); visited[u] = true; for (int i =0;i<adj[u].size();i++) { // Get vertex label and weight of current adjacent // of u. int v = adj[u][i].first; int weight = adj[u][i].second; if(!visited[v]) { // If there is shorted path to v through u. if (dist[v] > dist[u] + weight) { // Updating distance of v dist[v] = dist[u] + weight; pq.push(make_pair(dist[v], v)); } } } } vector<int>res; for(int i = 1;i<=n;i++) { if(i==s) continue; if(dist[i]==INT_MAX) { dist[i] = -1; } res.push_back(dist[i]); } return res;`

}

NerdyAditya + 0 comments We just have to use the edge with least weight right?

shu69bham + 0 comments thanks a lot :D that was the mistake i was making..

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

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

Mckowzie81 + 1 comment I have my output right and same as given in the question for test case 1 and rest but it is giving me result as wrong answer, while the test case 0 and test case 2 is correct.

karangada0 + 1 comment did u find a solution? i have the same problem

rbhambriiit + 0 comments most likely it is the output representation. all testcases need to be in a new row.

mohitkumar20 + 0 comments Thanks dude. 3 point of ur comment made my solution work for last case as well. thanks. :)

ulti72 + 0 comments ipasses 1st and last test case, but unable to do middlle ones, any example

y13uc154 + 0 comments Helped a lot!

serajam + 0 comments I was wondering what can I do with duplicates but didnt consider that I can filter it out when reading in the main func. Thanks! ^_^

ghazi_bousselmi + 0 comments 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 :)

sgrpwr + 0 comments Really, I was scratching my head due to this for 5 hours

Rys23 + 1 comment and if you code in Java use buffered reader

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

neromix188 + 0 comments LOL =))))))

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

samuele8 + 0 comments 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.

sgagandeep337 + 0 comments It cost me 10 fucking days.....

mithlesh42571 + 0 comments thank you!

DeepanshuBhatti + 4 comments Guys, after each test case print a new line

Keerthanss + 0 comments 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!

28rider + 0 comments Thanks Man!! really wasn't able to figure out the problem

majin_vegeta + 1 comment I was stuck for like an hour stuck because of this!

sgrpwr + 0 comments same here :p

seawolf001 + 0 comments 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; } }

mdakan + 6 comments I keep timing out on Test Case #7. In Java I'm using an arraylist of hashmaps to keep track of the edge weights, and a priority queue of neighbor vertices to select which to visit next.

Any general advice how to get it to perform faster? Let me know if I should just post the code.

mfry + 3 comments 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

mdakan + 2 comments That made the difference. The runtime for the other test cases almost cut in half. Thank you!

shamas + 0 comments How did you get this to work? I'm using Java 8 but FastScanner from https://github.com/jackyliao123/contest-programming/blob/master/Utils/FastScanner.java causes the "run code" to timeout? Which one did you use?

Edit: Solved it. HackerRank input must have changed. It just ends on an EOF. If you're using this FastScanner, you'll need to add to the end of token case with:

`if(bufferSize < 0 || c == (byte)'\n' || c =`

poonam2992 + 3 comments I am getting same timeout problem for c++. What should I do?

shamas + 0 comments [deleted]pandaBeta + 4 comments `ios::sync_with_stdio(false);`

this should be the very first line of main(); TestCase#7 is ~35MB. All time wasted in reading inputs...andrestirabo + 0 comments Thanks for that, I was having the same issue and that solved it

carna_viire + 0 comments Thank you so much!!

nima_trueway + 0 comments thank you sir ! thank you ! 3 days of headache, and finalyl I figured what was going wrong with my code.

kargarisaac + 0 comments Helped me to pass the final test case. Thanks. How should we know that? :D

sanglingjie + 1 comment 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!

mdakan + 1 comment I ended up re-adding nodes to the queue with their new priority rather than decreasing the key of nodes already present. This Stack Overflow post discusses some of the benefits of doing it the other way, but with java fast IO my solution was fast enough without it.

http://stackoverflow.com/questions/9255620/why-does-dijkstras-algorithm-use-decrease-key

sanglingjie + 2 comments Thanks a lot for replying! Did you use pq.remove() before re-adding? I read on this post that its time complexity is O(N) instead of O(logN)? http://stackoverflow.com/questions/12719066/priority-queue-remove-complexity-time

sanglingjie + 0 comments I tried just using PriorityQueue for this problem and tested for test7 on my own machine. Surprisingly, the running time is pretty much the same as using self-implemented hash-indexed heap..In big O analysis, the time complexity is supposed to be degrading from O(ElogV) to O(EV), but I guess the decrease-key is not called as frequent as I thought, especially I checked if it is indeed relaxed before deleting and adding. Thanks for the knowledge, this makes my life so much easier. :)

mdakan + 2 comments No problem! I didn't use pq.remove() for that reason. Instead I performed an additional check for whether a node was already visited after removing it from the queue.

Doing it this way means that your queue can get full of lots of low-priority nodes that you've already visited (which I think slows down adding nodes). That said, whichever instance of a node dequeues first is guaranteed to be the highest priority one, and dequeue is only O(1).

sanglingjie + 0 comments Nice! Even the queue grows to O(E), add to queue is still essentially O(logV). I guess the only concern is combining edges between same pairs of nodes, so E is bounded.

sanglingjie + 1 comment Sorry about being annoying. I rethought about this problem and felt there might be a caveat in this way. I think in Java, when we offer objects to a queue, it actually takes its reference. So if we re-offer a node to a queue, it actually stores two same thing: the old node's key secretly decreased, but the queue did not know that and did not deal with it. Then the order in the heap might be messed up, and "heapify" is not guarantee to push the newly added item to their correct position. Do you have any comments on this? Many thanks!

mdakan + 0 comments I think that might be beyond me. Maybe somebody else here can say more about exactly how the priority queue works. If not and you find other resources, please link to them!

pandaBeta + 0 comments The problem setter is cheater.

# Test case #7 has input file of 35MB

radim + 1 comment 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.

y13uc154 + 0 comments The first line helped a lot. I didn't believe initially, but now I see it has its effects. Thanks!

dwivediishere + 1 comment 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!

Tabby + 0 comments This worked for me too. Thanks for sharing.

mike_buttery + 0 comments [deleted]

thisisabhash + 2 comments Don't forget to print -1 for unreachable nodes instead of some max value.

kohei + 0 comments Thank you! I forgot about that!

mgperson + 1 comment 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.

davkh + 0 comments Thanks mate, the same problem I had.

ali_sezgin_cs + 3 comments Test case #7 times out. It seems like noone in the recent past has suffered from the same anomaly. Posting to say that if a similar thing is happening to your implementation, you are not alone. :)

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

ali_sezgin_cs + 0 comments Wow, that was odd; it did do the trick though. Thanks.

sauravmishra + 0 comments i also replaced cin/cout with printf and scanf still not passing test case 7..getting timeout.(used priority queue and list)..help!!

marcelogiesel + 5 comments You can also switch off the sync with printf/scanf and continue using cin/cout.

std::ios_base::sync_with_stdio(false);

anonomous + 0 comments Thanks! The sync_with_stdio trick saved my day! This is the oddest TLE I have encountered so far ...

dg_12345 + 0 comments Thank you so much! It worked. :)

ydflamingo + 0 comments Thank you so much. You are a tiny king.

liorcohen5 + 0 comments OMG I'd never even think of something like that! It actually worked! thanks!

mtsygankov + 0 comments Thanks for the hint!!! I got completely stuck into #7 timeout...

zukic07 + 0 comments thanks!!!!!

harshdeep27 + 0 comments Very nice trick...thanks

SidSethi + 0 comments [deleted]zen1986 + 1 comment Same thing happens in Java 7 & 8 for me. I submitted accepted answers by other people as my answer, TC7 timeout as well.

mk9440 + 2 comments Passed all test cases using FastReader i/o in java :D

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Scanner; import java.util.Stack; import java.util.StringTokenizer; public class Solution { static class FastReader { BufferedReader br; StringTokenizer st; public FastReader() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } String nextLine() { String str = ""; try { str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return str; } } public static void main(String[] args) { FastReader in=new FastReader(); int t1=in.nextInt(); for(int gj=0;gj<t1;gj++){ int n=in.nextInt(); int m=in.nextInt(); long w[][]=new long [n+1][n+1]; for (long[] row: w) Arrays.fill(row, 1000000l); for(int i=0;i<m;i++){ int x=in.nextInt(),y=in.nextInt(); long cmp=in.nextLong(); if(w[x][y]>cmp){ w[x][y]=cmp; w[y][x]=cmp; }} Stack <Integer> t=new Stack<Integer>(); int src=in.nextInt(); for(int i=1;i<=n;i++){ if(i!=src){t.push(i);}} Stack <Integer> p=new Stack<Integer>(); p.push(src); w[src][src]=0; while(!t.isEmpty()){int min=989997979,loc=-1; for(int i=0;i<t.size();i++){ w[src][t.elementAt(i)]=Math.min(w[src][t.elementAt(i)],w[src][p.peek()]+w[p.peek()][t.elementAt(i)]); if(w[src][t.elementAt(i)]<=min){ min=(int) w[src][t.elementAt(i)];loc=i;} } p.push(t.elementAt(loc));t.removeElementAt(loc);} for(int i=1;i<=n;i++){ if(i!=src && w[src][i]!=1000000l){System.out.print(w[src][i]+" ");} else if(i!=src){System.out.print("-1"+" ");} }System.out.println(); } }}

AKSaigyouji + 5 comments The final test case has 2500 nodes and over 3 million edges (almost all duplicates), and is quite strict about timing out. Using C# with a heap-based Dijkstra algorithm, Dijkstra's took about 10ms while the input-parsing took 2 seconds. Just the Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse) alone for the edges was enough to time it out. about 10-20% of that is the readline itself, and the rest is from parsing strings into ints.

Ultimately this seems to be an exercise in optimizing IO rather than a graph algorithm.

Edit: I played around with it and found a simpler way to improve parse run-time for C#. Create a dictionary that maps vertex strings to the corresponding parsed integer. i.e.

`var parse = new Dictionary<string, int>(); for (int i = 1; i <= n; i++){ parse[i.ToString()] = i; }`

Where n is the number of vertices as given in the problem. Then you can use parse[a] instead of int.Parse(a) for the vertices in each edge when you read them. Still have to use int.Parse for weights, since those can be very large. (I guess you could extend the dictionary up to 100000 (upper limit of weight) but that's a bit obscene). I found that this was sufficiently faster to avoid timing out.

Edit #2: An even simpler way to is to write your own string to int parser, as stevelang pointed out in a response to this post. The built-in one in C# is notoriously slow. This has the advantage of also working for edges.

shengliang_song + 0 comments 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

SidSethi + 0 comments [deleted]ericnorway + 0 comments Thanks! Parsing the vertices was causing mine to time out.

stevelang + 5 comments 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; }

kilicars + 0 comments Thank you very much for this! I could pass tc#7 after using this

psharm8 + 0 comments This works! Passed!!

AKSaigyouji + 0 comments That's probably the best approach to this issue. The reason C#'s built-in parse is so slow is that it has to check for all kinds of invalid input, which includes checking each char to ensure it's a digit. e.g. int.Parse will throw a FormatException if you feed it "32a1" while this method will return 3691, since 'a' gets converted to 49.

tiberiu_iancu + 0 comments This made the difference for me. Thanks!

NetMastr5 + 0 comments Thank you so much. Shaved off 0.05 sec (locally) for TC#7, and now it no longer times out.

barrypietersen + 0 comments 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

diekmann + 2 comments I'm trying to solve it in python3. But TC7 always times out. Once the input is parsed, my algorithm is fast.

The problem is that the complete code spends most of its time in the builtin

`int`

function of python to parse the huge amout of input.Any suggestions to speed up the reading of the input?

sash0 + 3 comments Try

`sys.stdin.readline()`

instead of`input()`

.l3arner_ + 1 comment Does the above optimization works, I am also seeing the same issue. I switched to sys.stdin.readline() .

diekmann + 3 comments Did not work for me :( Does it work for you? I feel the performance issue arises when converting the input to an

`int`

.The following parsing works for me (bottlenecks are:

`int`

conversion and selecting the min edge weight):numqueries = int(input()) for _ in range(numqueries): n, m = tuple(map(int, input().split())) edges = dict() for _ in range(m): u, v, r = readedge(sys.stdin.readline()) key = (u, v) if key in edges: edges[key] = min(r, edges[key]) else: edges[key] = r edges = [(u,v,r) for (u,v),r in edges.items()] startnode = int(input()) assert len(edges) <= m, (len(edges), m) print(" ".join(dijkstra(n, edges, startnode)))

l3arner_ + 0 comments I went for deduplication of edges while reading the inputs itself. that provided me enough speed up to pass the failing test case.

GeoMatt22 + 0 comments I did something similar in Python 3, but storing weights in a sparse adjacency matrix:

n, m = map(int, input().split()) W = defaultdict(dict) for _ in range(m): u, v, w = map(int, input().split()) W[u][v] = W[v][u] = min(w, W[u].get(v, wmax)) s = int(input())

mike_buttery + 0 comments I used a set to eliminate duplicates before converting to integer edge list.

I minimised weights as I parsed into a dictionary graph structure

`{u: {v:w, }, }`

karmamarga + 0 comments thanks for this python trick. after replacing input() with readline() my code passes all TC even without priority queue optimization

eloyekunle + 0 comments It's funny how this actually worked for me.

ntrinquier + 0 comments 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.

old_mountain + 0 comments For people using c++ (std::cin, std::cout, specifically) and getting timeout on 7, remember to turn off synchronization with the standard C stream objects:

std::ios_base::sync_with_stdio(false);

That did the trick for me (no need to change your code to scanf and printf)

king_geedorah + 2 comments I'm getting Wrong Answer for all test cases except for #0. I've diff'd my output against #1 and #6 on my local machine and it's exactly the same. Does anyone have suggestions? Here's a link to my submission.

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

simonezandara + 1 comment I have the same issue. Using Java

johand84 + 0 comments The same issue. Here is the result for the last case, exactly as a correct answer, but still fails: 3 6 4 5 5 4 5 4 3 3 4 6 6 4 4 4 4 5 3 4 5 3 4 6 8 4 5 3 4 4 6 4 6 6 2 4 6 4 4 4 4 5 5 3 4 5 3 6 5 4 5 5 4 4 5 3 3 4 2 3 5 2 4 4 3 4 10 5 5 7 4 4 4 1 4 4 4 5 4 4 5 4 4 5 4 5 6 5 4 4 5 5 5 4 4 4 4 3 4 5 3 3 5 4 6 8 2 5 3 4 4 5 3 5 3 3 4 5 3 6 5

ivarmu + 0 comments 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.

rohitanand_iitk1 + 1 comment Abort called at 0.34s in last testcase.What does it mean?

xnuter + 0 comments [deleted]

Sort 359 Discussions, By:

Please Login in order to post a comment