Category Dijkstra

SPOJ – EZDIJKST – Easy Dijkstra Problem

Arunima Mandal Leave a comment

Problem: https://www.spoj.com/problems/EZDIJKST/

Note: This is a pretty straightforward problem of basic Dijkstra implementation.

In case of the Wrong Answer:

  1. Notice that the input is a Directed graph, not an undirected graph. Take care of it while creating the adjacency matrix of the graph.
  2. Notice that while pushing in the priority queue, you should push the updated cost of the current node as the first element of the pair and then the node itself as the 2nd element of the pair.

In case of the Time Limit Exceeded:

The funny thing in my case is, I got the time limit exceeded because I declared the Dijkstra function as int but was not returning any integer at first, instead I was directly printing the output inside that function. I had no idea that this fault can result in a “time limit exceeded” verdict. As I didn’t notice that at first, I debugged the code for so much time, and lastly noticed that the return type of the function should be void as I was not returning anything there. That fix made my code Accepted in SPOJ! Later, I kept the function type as int and returned the result from there.

Code:

#include <bits/stdc++.h>

#define INF             INT_MAX
#define MAX             10004
#define pii             pair<int,int>

using namespace std;

int dijkstra(int src, int dst, vector<vector<pii>> &adj)
{
    vector<int> dis(MAX, INF);
    dis[src]=0;

    priority_queue<pii, vector<pii>, greater<pii> >pq;
    pq.push({0, src}); // Insert source in priority queue and initialize its distance as 0.

    while(!pq.empty())
    {
        int u=pq.top().second;
        int cost=pq.top().first;
        pq.pop();

        //Optimization in priority queue:
        //Since the pq can hold same node more than once with different costs,
        //no need to process the nodes which has already been updated to shorter distance
        if(dis[u]<cost) continue;

        for(int i=0; i<adj[u].size(); i++)
        {
            int v=adj[u][i].first;
            cost=adj[u][i].second;

            if(dis[v]>dis[u]+cost)
            {
                dis[v]=dis[u]+cost;
                pq.push({dis[v], v});
            }
        }
    }
    return dis[dst];
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    for(int z=0; z<t; z++)
    {
        int node,edge;
        cin>>node>>edge;

        vector<vector<pair<int,int> > > adj(MAX);

        for(int i=0; i<edge; i++)
        {
            int from,to,cost;
            cin>>from>>to>>cost;
            adj[from].push_back({to, cost});
            //adj[to].push_back({from, cost}); //If undirected graph
        }

        int src,dst;
        cin>>src>>dst;

        int min_distace=dijkstra(src, dst, adj);

        if(min_distace==INF) cout<<"NO"<<endl;
        else cout<<min_distace<<endl;
    }
    return 0;
}