SPOJ Solution-SHPATH The Shortest Path-Solution in C, C++, Java, Python

s [the number of tests <= 10]
n [the number of cities <= 10000]
NAME [city name]
p [the number of neighbours of city NAME]
nr cost [nr - index of a city connected to NAME (the index of the first city is 1)]
        [cost - the transportation cost]
r [the number of paths to find <= 100]
NAME1 NAME2 [NAME1 - source, NAME2 - destination]
[empty line separating the tests]

Input:
1
4
gdansk
2
2 1
3 3
bydgoszcz
3
1 1
3 1
4 4
torun
3
1 3
2 1
4 1
warszawa
2
2 4
3 1
2
gdansk warszawa
bydgoszcz warszawa

Output:
3
2

#1 Code Example with C++ Programming

Code - C++ Programming

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
#define INF (1<<25)

map<string,int> city;
vector<vii> neighbors;
vector<int> vals;
int n;

typedef bool (*comp)(ii,ii);

bool compare(ii a,ii b){
	return a.second>b.second;
}

void dijkstras(int source,int destination){
	priority_queue<ii,vii,comp> pq(compare);
	pq.push(ii(source,0));
	vals[source]=0;
	while(!pq.empty()){
		ii x = pq.top();
		int top=x.first;
		pq.pop();
		if(top==destination)break;
		if(vals[top]<x.second){
			continue;
		}
		for(int i=0;i<neighbors[top].size();++i){
			ii neighbor = neighbors[top][i];
			int in = neighbor.first, cost = neighbor.second;
			if(vals[in]>vals[top]+cost){
				vals[in]=vals[top]+cost;
				pq.push(ii(in,vals[in]));
			}
		}
	}
}


int main(){
	int s;
	scanf("%d",&s);
	city.clear();
	while(s--){
		scanf("%d",&n);
		neighbors = vector<vii> (n,vii());
		for(int i=0;i<n;++i){
			char name[11];
			scanf("%s",name);
			city[string(name)]=i;
			int inn;
			scanf("%d",&inn);
			while(inn--){
				int nr,cost;
				scanf("%d%d",&nr,&cost);
				neighbors[i].push_back(ii(nr-1,cost));
			}
		}
		int r;
		scanf("%d",&r);
		while(r--){
			char source[11],destination[11];
			scanf("%s %s",source,destination);
			vals = vi(n,INF);
			string start = string(source);
			string end = string(destination);
			dijkstras(city[start],city[end]);
			printf("%d\n",vals[city[end]]);
		}
	}
	return 0;
}

Copy The Code & Try With Live Editor

Input

Output