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

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

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

    adjList.assign(N,edge_vect());

    for(int i=0; i < E; i++)
    {
        scanf("%d %d %d", &start, &end, &w);
        adjList[start].push_back(edge(end,w));
        adjList[end].push_back(edge(start,w));
    }
        
    //Dijkstra algorithm
    visited.assign(N,false);
    dist_to.assign(N,INF);
    priority_queue<edge,vector,greater> pq;

    dist_to[S] = 0;
    pq.push(edge(0,S));

    while(!pq.empty())
    {
        edge e=    pq.top();
        pq.pop();
        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;
                    pq.push(edge(dist_to[v.first],v.first));
                }
            }            
    }

    printf("Case #%d: ",tc);        
    if(dist_to[T] != INF)
        printf("%d\n",dist_to[T]);
    else
        printf("%s\n","unreachable");
        
}    
 
return (0);
}

Java solution:


//TL
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;
    }
    
    @Override
    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);        
        if(isReachable)
            System.out.printf("%d%n",dist);
        else
            System.out.println("unreachable");
    }
    
    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();
            
            if(numOfEdges==0)
            {
                printOutput(tc, false, 0);
                continue;
            }
            
            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;
            queue.add(vertexes.get(source));    
            
            Vertex u,v;        
            while(!queue.isEmpty())
            {
                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;    
                        queue.add(v);                        
                    }
                }
            }            
            
            printOutput(tc, vertexes.get(dest).IsVisited,  vertexes.get(dest).distFromSrc);                
            
        }                

    }

}

Sample input
3
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

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: