uva: 11060 – Beverages (Topological sort)

11060 - Beverages (Topological sort)

#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <string>
//#include <conio.h>

using namespace std;

typedef pair<string,int> namval;
typedef pair<int,string> valnam;
typedef vector vi;

struct compareval
{
	bool operator()(const int& a, const int& b)
	{
		return a > b;
	}
};

int main()
{
	int vertex, edge,tc=0;
	string str, start, end;

	while(scanf("%d", &vertex)==1)
	{
		map<string,int> name_value;
		map<int, string> value_name;

		for(int i=0; i < vertex; i++)
		{
			cin>>str;
			name_value.insert(namval(str, i));
			value_name.insert(valnam(i, str));
		}

		scanf("%d", &edge);
		vector adjList;
		adjList.assign(vertex,vi());

		vi indegree = vi(vertex);
		indegree.assign(vertex,0);

		for(int i=0; i < edge; i++)
		{
			cin>>start;
			cin>>end;

			int u = name_value.find(start)->second;
			int v = name_value.find(end)->second;

			adjList.at(u).push_back(v);
			indegree[v] +=1;
		}

		priority_queue<int, vector<int>, compareval> pq;

		for(int i=0; i < vertex; i++)
		{
			if(indegree[i] == 0)
			{
					pq.push(i);
			}
		}

		vi order = vi();

		while(!pq.empty())
		{
			int u = pq.top(); pq.pop();
			order.push_back(u);

			for(int i=0; i < adjList[u].size(); i++)
			{
				 int v = adjList[u][i];
			 	 indegree[v]--;
				 if(indegree[v]==0 )
						 pq.push(v);
			}
		}

		printf("Case #%d: Dilbert should drink beverages in this order: %s",++tc, value_name[order[0]].data() );
		for(int i = 1; i < order.size(); i++)
		{
			printf(" %s",  value_name[order[i]].data());
		}
		printf(".\n\n");
	}
	//getch();
return 0;
}

//
/*

http://uva.onlinejudge.org/external/110/11060.html

Sample Input

3
vodka
wine
beer
2
wine vodka
beer wine

5
wine
beer
rum
apple-juice
cachaca
6
beer cachaca
apple-juice beer
apple-juice rum
beer rum
beer wine
wine cachaca

10
cachaca
rum
apple-juice
tequila
whiskey
wine
vodka
beer
martini
gin
11
beer whiskey
apple-juice gin
rum cachaca
vodka tequila
apple-juice martini
rum gin
wine whiskey
apple-juice beer
beer rum
wine vodka
beer tequila

Sample Output

Case #1: Dilbert should drink beverages in this order: beer wine vodka.

Case #2: Dilbert should drink beverages in this order: apple-juice beer wine rum cachaca.

Case #3: Dilbert should drink beverages in this order: apple-juice wine vodka beer rum cachaca tequila whiskey martini gin.

*/

uva: 10305 Ordering Tasks ( Topological sort )

10305 Ordering Tasks ( Topological sort )

Problem and solution –

import java.io.IOException;
import java.util.PriorityQueue;
import java.util.Queue;


class Main_10305_OrderingTasks {
	
	static String readInputLine() throws IOException
	{

		int byt,index=0;
		byte[] bytes= new byte[255];

		while(true)
		{
			byt = System.in.read();
			if(byt==-1 || byt =='\n') break;
			bytes[index++] += byt;
		}

		if(bytes.length==0) return null;

		return new String(bytes);
	}

	public static void main(String[] args) throws IOException {
		String line;
		String[] tempArr;
		int vertex, edge, u,v;
		int[][] graph;
		int[] indegree;
		StringBuilder order;
		Queue q = new PriorityQueue(100+1);

		while(true)
		{

			line = readInputLine();
			if(line == null) break;

			tempArr = line.trim().split(" ");
			vertex = Integer.parseInt(tempArr[0]);
			edge = Integer.parseInt(tempArr[1]);

			if(vertex ==0) break;

			graph = new int[vertex+2][vertex+2];
			indegree = new int[vertex+1];
			order = new StringBuilder();
			
			for(int i=1; i<=edge; i++)
			{
				tempArr=  readInputLine().trim().split(" ");
				u = Integer.parseInt(tempArr[0]);
				v = Integer.parseInt(tempArr[1]);

				graph[u][v] = 1;
				indegree[v] +=1;
			}	

			//start processing tasks/vertex
			q.clear();
			while(true)
			{
				u=v=-1;
				for(int i=1; i<=vertex; i++)
				{
					if(indegree[i] == 0 )
					{		
						q.add(i);
						indegree[i] = -1; //task in queue
						order.append(i+" ");//output data											
					}
				}
				
				//if no task to process then break
				if(q.isEmpty()) break;
				u = q.poll();
				//reduce indegree from source/u task to dependent tasks
				for(v=0; v <= vertex; v++)
				{
					if(graph[u][v]==1) 
					{
						graph[u][v] = 0;
						indegree[v] -= 1;
					}
				}
			}
			//output tasks order
			System.out.println(order.toString().trim() );
			
		}
		//System.out.println(str);
	}

}




/*

Sample Input

5 4
1 2
2 3
1 3
1 5
0 0
Sample Output

1 4 2 5 3

*
*/

uva: 11831 Sticker Collector Robots

Problem and solution analysis: it is simple graph traversal problem.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


 class Main_11831_StickerCollectorRobots {

	/**
	 * TL
	 * Graph Traversal
	 * http://uva.onlinejudge.org/external/118/11831.html
	 * 
	 * `.' -- normal cell;
`*' -- cell which contains a sticker;
`#' -- cell which contains a pillar;
`N' - North, `S' - South, `L' - EAST, `O' - West -- cell where the robot starts the rally

D -``turn 90 degrees to the right"
E- ``turn 90 degrees to the left" 
F - ``move forward one cell"
	 */
	
	
	private  static  final char RIGHT='D',LEFT='E', MOVE='F';
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String dirs = "NLSO";//NESW
		int[] dr = {-1,0,1, 0};//NESW
		int[] dc = { 0,1,0,-1};//		
		char[][] graph;
		int NRow, MCol, SIns, stickerCount, index;
		int currentDir, currentRow, currentCol, newr, newc;		
		String instruction;
		String[] strArray;
		char ch;
		

		while(true)
		{
			strArray = br.readLine().trim().split(" ");
			
			NRow = Integer.parseInt(strArray[0]);
			if(NRow == 0) break;

			MCol = Integer.parseInt(strArray[1]);
			SIns = Integer.parseInt(strArray[2]);			
			currentRow = 0;
			currentCol =0;
			currentDir = 0;
			graph = new char[NRow][MCol];
			
			for(int i=0; i < NRow; i++)
			{				
				graph[i] = br.readLine().trim().toCharArray();

				for(int j=0; j < MCol; j++)
				{					
					index = dirs.indexOf(graph[i][j]);
					if(index>=0)
					{						
						currentDir = index;
						currentRow = i;
						currentCol = j;							
					}
				}
			}

			instruction = br.readLine().trim();
			stickerCount = 0;
			for(int i=0; i < SIns; i++)
			{
				ch = instruction.charAt(i);
				if(ch==RIGHT )
					currentDir= (currentDir + 1) % 4;
				else if(ch == LEFT)
					currentDir= (currentDir + 3) % 4;
				else if(ch == MOVE)
				{
					newr = currentRow +  dr[currentDir];
					newc = currentCol + dc[currentDir];
					if(newr>=0 && newc>=0 && newr < NRow && newc < MCol && graph[newr][newc] != '#')
					{						
						if(graph[newr][newc]=='*')
						{
							stickerCount++;
							graph[newr][newc] = '.';							
						}
						currentRow = newr;
						currentCol = newc;
					}
				}
			}
			
			System.out.println(stickerCount);
		}
	}
}

/*

 Sample Input 

3 3 2
***
*N*
***
DE
4 4 5
...#
*#O.
*.*.
*.#.
FFEFF
10 10 20
....*.....
.......*..
.....*....
..*.#.....
...#N.*..*
...*......
..........
..........
..........
..........
FDFFFFFFEEFFFFFFEFDF
0 0 0

Sample Output 

0
1
3


 * */

uva: 10405 – Longest Common Subsequence (LCS)

10405 – Longest Common Subsequence

Problem analysis:

Given two sequences of characters, print the length of the longest common subsequence of both sequences. For example, the longest common subsequence of the following two sequences:

abcdgh
aedfhr

is adh of length 3.

Solution analysis:

• LCS – solution of this problem is standard LCS  algorithm

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.lang.System;

class Main_10405_LCS {
    /**
     * Author: Mohammad Moniruzzaman
     * UVa ID: 457490     
     */

    public static void main(String[] args) {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(br);
        String str1, str2;
        int[][] lcs;
        int i,j,m,n;
        
        while(sc.hasNext())
        {
            str1 = sc.nextLine();
            str2 = sc.nextLine();
            m = str1.length();
            n = str2.length();
            
            lcs = new int[m+1][n+1];
            
            for(i=1; i <= m; i++)
            {
                for(j=1; j <= n; j++)
                {
                    if(str1.charAt(i-1) == str2.charAt(j-1))
                    {
                        lcs[i][j] = lcs[i-1][j-1] + 1;
                    }
                    else
                    {
                        lcs[i][j] = Math.max( lcs[i-1][j], lcs[i][j-1] );
                    }                    
                }
            }
            System.out.println(lcs[m][n]);            
        }
        sc.close();
        sc = null;
    }

}

uva: 10066 – The Twin Towers ( LCS )

10066 – The Twin Towers

Problem analysis:

•  Given the descriptions of two dissimilar towers you are asked only to find out the number of tiles in the highest twin towers that can be built from them.
• For each pair of towers in the input first output the twin tower number followed by the number of tiles (in one tower) in the highest possible twin towers that can be built from them. Print a blank line after the output of each data set.

Soltion analysis:

•  LCS – solution of this problem is standard LCS  algorithm

C++ solution:

#include<stdio.h>

#define MAX 100
#define max(a,b) ((a)<(b) ? (b):(a))

int N1, N2;
int firstT[MAX+1];
int secondT[MAX+1];
int c[MAX+1][MAX+1];
int lcsLength, nCase;

int main10066()
{
	int i,j;

	//int firstT[MAX]={0};
	//int secondT[MAX]={0};

	while(true)
	{
		scanf("%d %d", &N1, &N2);

		if(N1 ==0 && N2==0) break;

		for(i=1; i<=N1; i++)
			scanf("%d",&firstT[i]);

		for(i=1; i<=N2; i++)
			scanf("%d",&secondT[i]);

		/*for(i=0;i <=N1; i++)
			for(j=0;j<=N2; j++)
				c[i][j] = 0;*/

		for(i=1; i<= N1; i++)
			for(j=1; j<= N2; j++)
			{
				if(firstT[i] == secondT[j])
				{
					c[i][j] = c[i-1][j-1] + 1;
				}
				else
				{
					c[i][j] = max(c[i-1][j], c[i][j-1]);
				}
			}

		printf("Twin Towers #%d\n",++nCase);
		printf("Number of Tiles : %d\n\n",c[N1][N2]);
	}
return 0;
}

Sample Input
7 6
20 15 10 15 25 20 15
15 25 10 20 15 20
8 9
10 20 20 10 20 10 20 10
20 10 20 10 10 20 10 10 20
0 0

Sample Output
Twin Towers #1
Number of Tiles : 4

Twin Towers #2
Number of Tiles : 6

uva: 11631 Dark Roads ( MST – Prim)

11631 Dark Roads

Problem analysis:

• There will still be at least one illuminated path from every junction (vertex) in Byteland to every other junction(vertex)
•  What is the maximum daily amount of money the government of Byteland can save, without making their inhabitants feel unsafe?
• Connecting all the vertexes/nodes with minimum  lighting costs  and finding saving of operating roads lighting

Solution Hints:

• This problem can be solved using Minimum Spanning Tree (MST) Prim’s, Kruskal’s  algorithms   –
  • Here it is solved using Prim’s
• Firstly, find the total costs of roads lighting
• Secondly, find the minimum costs at least one illuminated path for connecting all junctions (vertexes)
• Then, daily saving is deduction minimum costs from total costs.

Solution in Java and C++ are as follows:

 Solution in Java:

//TL
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class EdgeDR implements Comparable
{
    int u;
    int v;
    int w;    
    public EdgeDR(int u, int v, int w)
    {
        this.u = u;
        this.v = v;
        this.w = w;
    }

    @Override
    public int compareTo(EdgeDR other) {        
        return this.w - other.w;
    }
}

class VertexDR implements Comparable
{
    int id;
    int key;
    public VertexDR(int id, int key)
    {
        this.id = id;
        this.key = key;
    }

    @Override
    public int compareTo(VertexDR other) {
        return this.key - other.key;
    }
}

class Main_11631_DarkRoads_MST_Prims {

    public static void main(String[] args) {        
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(br);
        
        final int INF = Integer.MAX_VALUE;
        int V,E, v1, v2,u, w;
        int totalCost, minCost;            
        int[] key;        
            
        ArrayList mstTree;
        ArrayList<arraylist<EdgeDR>> graph;
        PriorityQueue pq;

        while(true)
        {
            V = sc.nextInt();
            E = sc.nextInt();

            if(V==0) break;            

            totalCost = 0;        
            key= new int[V];
            pq =  new PriorityQueue(V);
            mstTree = new ArrayList(V);
            graph =  new ArrayList<ArrayList<EdgeDR>>(V);

            Arrays.fill(key, INF);

            for(int i=0; i
            {
                graph.add(new ArrayList<EdgeDR>());                    
            }

            for(int i=0;i<E;i++)
            {
                v1 = sc.nextInt();
                v2 = sc.nextInt();
                w = sc.nextInt();

                totalCost += w;
                graph.get(v1).add(new EdgeDR(v1,v2,w));
                graph.get(v2).add(new EdgeDR(v2,v1,w));                
            }    

            minCost = 0;
            key[0] = 0;            
            pq.add(new VertexDR(0,0));

            while(!pq.isEmpty())
            {        
                u = pq.poll().id;
                if(!mstTree.contains(u))
                {
                    minCost += key[u];
                    mstTree.add(u);
                }
                
                for(EdgeDR e:graph.get(u))
                {
                    if(!mstTree.contains(e.v) && e.w < key[e.v])
                    {
                        key[e.v] = e.w;                            
                        pq.add(new VertexDR(e.v, key[e.v]));
                    }
                }

            }

            System.out.println(totalCost - minCost);
        }

    }

}

Solution in C++:

c++ code here

Sample Input

7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11
0 0

Sample Output

51

 

 

uva: 544 – Heavy Cargo ( Floyd Warshall MaxiMin )

544 – Heavy Cargo

Problem analysis:

• Given start and destination city, your job is to determine the maximum load of the Godzilla V12 so that there still exists a path between the two specified cities.

Solution analysis:

• It is solvable using Floyd Warshall Maximin algorithm

Java solution:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Hashtable;
import java.util.Map;
import java.util.Scanner;

class Main_544_HeavyCargo {

    /**
     * Author: Mohammad Moniruzzaman    
     */

    public static void main(String[] args) {
        final int INF = Integer.MIN_VALUE;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(br);

        Map<String, Integer> cities;
        String line, start, end;
        int numVertexes, numEdges, load, testCase=0,source, dest;
        int[][] graph;

        while(true)
        {
            testCase++;

            numVertexes = sc.nextInt();
            numEdges = sc.nextInt();

            if(numVertexes ==0 ) break;

            cities =  new Hashtable<string, integer="">(numVertexes);
            graph = new int[numVertexes+1][numVertexes+1];

            for(int i=0; i < numVertexes; i++)
                for( int j=i; j < numVertexes; j++)
                    graph[i][j] = graph[j][i] = INF;
            
            //skip empty line
            sc.nextLine();
            
            for(int i=0; i < numEdges ; i++)
            {
                line = sc.nextLine();

                start = line.split(" ")[0];
                end = line.split(" ")[1];
                load = Integer.parseInt(line.split(" ")[2]);
                
                if(! cities.containsKey(start)) cities.put(start, cities.size());
                
                if(! cities.containsKey(end)) cities.put(end, cities.size());
                
                graph[cities.get(start)][cities.get(end)] = load;    
                graph[cities.get(end)][cities.get(start)] = load;
            }

            line = sc.nextLine();

            source = cities.get( line.split(" ")[0]);
            dest = cities.get(line.split(" ")[1]);

            ///Floyd-Warshall - MaxiMin            
            for(int k=0; k < numVertexes; k++)
                for(int i=0; i < numVertexes; i++)
                    for(int j=0; j < numVertexes; j++)
                    {
                        if(graph[i][k] != INF && graph[k][j] != INF)
                        {
                            graph[i][j] = Math.max(graph[i][j], Math.min(graph[i][k], graph[k][j]));
                        }
                    }

            System.out.printf("Scenario #%d%n",testCase);
            System.out.printf("%d tons%n%n",graph[dest]);
        }

    }

}

 

Sample Input 

4 3
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Muenchen
5 5
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Hamburg 220
Hamburg Muenchen 170
Muenchen Karlsruhe
0 0

Sample Output 

Scenario #1
80 tons

Scenario #2
170 tons

 

uva: Cow Contest ( Floyd Warshall – Transitive Closure)

Cow Contest

 

Problem :

N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.

The contest is conducted in several head to head rounds, each between two cows. If cow A has a greater skill level than cow B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B), then cow A will always beat cow B.

Farmer John is trying to rank the cows by skill level. Given a list the results of M (1 ≤ M ≤ 4,500) two cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.

Input

The input contains multiple test cases, until the end of file. Each test case is given in the following order:

• Line 1: Two space separated integers: N and M
• Lines 2..M+1: Each line contains two space separated integers that describe the competitors and results (the first integer, A, is the winner) of a single round of competition: A and B

Output

For each test case, output in a single line, a single integer representing the number of cows whose ranks can be determined.

 

 

Solution analysis:

• It is problem of Transitive Closure 
• It can be solved using modified Floyd Warshall Transitive Closure algroritm

 

 C++ Solution:

#include <stdio.h>
#define NMAX 100

int beating[NMAX+1][NMAX+1];

int main()
{
	int m,n,i,j,k,result;

	while(EOF != scanf("%d %d", &n, &m))
	{

		for(i=0; i < n; i++)
		{
			for(j=0; j < n; j++)
			{
				beating[i][j] = 0;
			}
			beating[i][i] = 1;
		}

		while(m--)
		{
			scanf("%d %d",&i,&j);
			beating[--i][--j] = 1;
		}

	for(k=0; k < n; k++)
		for(i=0; i< n; i++)
			for(j=0; j < n; j++)
			{
				if( beating[i][k] &&  beating[k][j] )
				{
					beating[i][j] = 1;
				}
			}

	result = 0;
	for(i=0;i < n ; i++)
	{
		int nReachable=0;

		for(j=0; j < n; j++)
		{
			nReachable+= beating[i][j] + beating[j][i];
		}

		if(nReachable == n+1 ) result++;
	}

		printf("%d\n", result);
	}

	return 0;
}

 

 

Sample Input

5 5
4 3
4 2
3 2
1 2
2 5

Sample Output

2

uva: 558 – Wormholes ( Bellman-Ford )

558 – Wormholes  ( Bellman-Ford )

 

Problem analysis:

• The scientist wants to reach a cycle of wormholes somewhere in the universe that causes her to end up in the past
• Write a program to find out whether such a cycle exists

Solution analysis:

• Find if there is any negative cycle in the path, then there will be path to end up in the past
• Using  Bellman-Ford algorithm it can be solved, if there is any negative cycle then it is “possible” ,  otherwise “not possible”

 

Java solution:

          

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

class Edge
{
    public int u;
    public int v;
    public int w;
    public Edge(int source, int target, int weight)
    {
        this.u = source;
        this.v= target;
        this.w =weight;
    }
}

class BellmanFord
{
    public final int INFINITY=Integer.MAX_VALUE;
    private int mNumOfVertexes, mSource, mDestination;
    private int mDistances[];
    private    ArrayList mEdges;
    private boolean mHasNegativeCycle;
    
        
    public BellmanFord(int numofvertexes, ArrayList edges)
    {
        this.mNumOfVertexes = numofvertexes;        
        this.mEdges = edges;
    }
    
    public int costSourceToDest(int src, int dest)
    {
        bfAlgorithm(src,dest);
                
        return mDistances[dest];            
    }

    public boolean hasNegativeCycle(int src, int dest)
    {
                
        bfAlgorithm(src,dest);
        
        return mHasNegativeCycle;
    }

    private void bfAlgorithm(int src, int dest)
    {
        
        mSource = src;
        mDestination = dest;
        
        int numvrtx = mNumOfVertexes;
        
        mDistances = new int[numvrtx+1];        
        for(int i=0;i<=numvrtx;i++)
            mDistances[i]=INFINITY;

        mDistances[mSource] = 0;
        mHasNegativeCycle=false;
        for(int level=1; level<=numvrtx; level++)
        {
            for(Edge edg:mEdges)
            {
                if(mDistances[edg.u]+ edg.w < mDistances[edg.v])
                {
                    mDistances[edg.v] = mDistances[edg.u]+ edg.w;

                    if(level==numvrtx)
                        mHasNegativeCycle=true;
                }
            }
        }        
    }

}

class Main_Wormholes_558_BellmanFord {    

    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, target, weight;
        
        ArrayList<Edge> edges;        
        BellmanFord blmnfrd;
        
        for(int tc=1; tc<=testCase; tc++)
        {
            numofvertexes = sc.nextInt();
            numofedges = sc.nextInt();

            edges = new ArrayList<Edge>();                

            for(int i=1;i<=numofedges;i++)
            {
                source = sc.nextInt();
                target = sc.nextInt();
                weight= sc.nextInt();
                edges.add(new Edge(source,target,weight));            
            }
            
            blmnfrd = new BellmanFord(numofvertexes, edges);
            
            if(blmnfrd.hasNegativeCycle(0, numofvertexes-1))
                System.out.println("possible");
            else
                System.out.println("not possible");

        }
        System.out.flush();
        sc.close();
        sc=null;
    }

}

Sample Input

2
3 3
0 1 1000
1 2 15
2 1 -42
4 4
0 1 10
1 2 20
2 3 30
3 0 -60

Sample Output

possible
not possible

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