uva: 10986 – Sending email ( Dijkstra )

10986 – Sending email

Problem analysis:

  •  There are n SMTP servers connected by network cables. Each of the m cables connects two computers and has a certain latency measured in milliseconds required to send an email message.
  • What is the shortest time required to send a message from server S to server T along a sequence of cables? Assume that there is no delay incurred at any of the servers.

Solution analysis:

  • Find shortest time from source to destination
  • This problem’s can be solve using Dijkstra algorithm


 C++ solution :

#include <stdio.h>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;

#define INF 1e9

typedef pair<int,int> edge;
typedef vector edge_vect;
typedef vector vi;

vector adjList;
vi dist_to;
vector<bool> visited;

//struct compare  
//  bool operator()(const int& l, const int& r)  
//  {  
//      return l > r;  
//  }  

// with visited[] array 2.06sec, except 1.95 sec

int main10986()
int testCase, N, E, S, T;
int start, end, w,d,u,v;
for(int tc=1; tc <= testCase; tc++)
    scanf("%d %d %d %d",&N,&E,&S,&T);


    for(int i=0; i < E; i++)
        scanf("%d %d %d", &start, &end, &w);
    //Dijkstra algorithm
    priority_queue<edge,vector,greater> pq;

    dist_to[S] = 0;

        edge e=    pq.top();
        u = e.second;
        d = dist_to[e.second];    
        visited[u] = true;

            for(int i=0; i < adjList[u].size();i++)
                edge v = adjList[u][i];
                if(!visited[v.first] && d + v.second < dist_to[v.first])
                    dist_to[v.first] = d + v.second;

    printf("Case #%d: ",tc);        
    if(dist_to[T] != INF)
return (0);

Java solution:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

class Vertex implements Comparable<Vertex>
    //vertex u
    public int id;
    //adjacency list with u - list of edges
    public ArrayList adjList;
    //distance from source to this vertex (u -> v)
    public int distFromSrc;
    //is it visited or in shortest path set
    public boolean IsVisited;
    //previous vertex, path from source to this vertex
    //public Vertex prev;
    public Vertex(int id)
        this.id = id;
        adjList = new ArrayList<Edge>();    
        distFromSrc = Integer.MAX_VALUE;
        IsVisited = false;
    public int compareTo(Vertex other) {
        return this.distFromSrc - other.distFromSrc;

class Edge
    public int v;
    public int w;
    public Edge(int v, int w)
        this.v = v;
        this.w = w;

class Main_10986_SendingEmail_Dijkstra_2_TL {
    private static void printOutput(int tc, boolean isReachable, int dist)
        System.out.printf("Case #%d: ",tc);        
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(br);
        int testCase = sc.nextInt();
        int numOfVertexes, numOfEdges, source, dest;            
        ArrayList vertexes;
        for(int tc = 1; tc<=testCase; tc++)
            numOfVertexes = sc.nextInt();
            numOfEdges = sc.nextInt();
            source = sc.nextInt();
            dest = sc.nextInt();
                printOutput(tc, false, 0);
            vertexes = new ArrayList(numOfVertexes+1);
            for(int i=0;i
             vertexes.add(i,new Vertex(i));
            for(int i=0; i<numOfEdges; i++)
                int u,v,w;
                u = sc.nextInt();
                v = sc.nextInt();
                w = sc.nextInt();    
                vertexes.get(u).adjList.add(new Edge(v,w));
                vertexes.get(v).adjList.add(new Edge(u,w));
            //Dijkstra    algorithm    
            PriorityQueue<Vertex> queue = new PriorityQueue<Vertex>();
            vertexes.get(source).distFromSrc = 0;
            Vertex u,v;        
                u = queue.poll();
                u.IsVisited = true;                
                if(u.id == dest) break;
                for(Edge edge:u.adjList)
                    v = vertexes.get(edge.v);                    
                    if(u.distFromSrc + edge.w  < v.distFromSrc)
                        v.distFromSrc = u.distFromSrc + edge.w;    
            printOutput(tc, vertexes.get(dest).IsVisited,  vertexes.get(dest).distFromSrc);                



Sample input
2 1 0 1
0 1 100
3 3 2 0
0 1 100
0 2 200
1 2 50
2 0 0 1
Sample output
Case #1: 100 
Case #2: 150 
Case #3: unreachable


About M Moniruzzaman
A passionate software engineer, have been developing applications on various platforms such as Android, iPhone, .Net (C#) technologies and web based ASP.NET, PHP, JavaScript, jQuery technologies for more than 10 years. Especially I have expertise on developing applications for Android and iPhone, as well as service oriented, client-server based applications where clients will be reside on Android/iPhone that communicate with WCF(.NET) service hosted on server. I have completed certification in Microsoft Certified Professional Developer (MCPD) on .Net 4 . I have completed my graduation in -- B.Sc. (Engineering) in Computer Science and Engineering, ShahJalal University of Science and Technology, Bangladesh. Thanks, M. Moniruzzaman (Zaman)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: