Algorithm
Problem link- https://www.spoj.com/problems/COURIER/
COURIER - The Courier
Byteland is a scarcely populated country, and residents of different cities seldom communicate with each other. There is no regular postal service and throughout most of the year a one-man courier establishment suffices to transport all freight. However, on Christmas Day there is somewhat more work for the courier than usual, and since he can only transport one parcel at a time on his bicycle, he finds himself riding back and forth among the cities of Byteland.
The courier needs to schedule a route which would allow him to leave his home city, perform the individual orders in arbitrary order (i.e. travel to the city of the sender and transport the parcel to the city of the recipient, carrying no more than one parcel at a time), and finally return home. All roads are bi-directional, but not all cities are connected by roads directly; some pairs of cities may be connected by more than one road. Knowing the lengths of all the roads and the errands to be performed, determine the length of the shortest possible cycling route for the courier.
Input
The input begins with the integer t, the number of test cases. Then t test cases follow.
Each test case begins with a line containing three integers: n m b, denoting the number of cities in Byteland, the number of roads, and the number of the courier's home city, respectively (1<=n<=100,1<=b<=m<=10000). The next m lines contain three integers each, the i-th being ui vi di, which means that cities ui and vi are connected by a road of length di (1<=ui,vi<=100, 1<=di<= 10000). The following line contains integer z - the number of transport requests the courier has received (1<=z<=5). After that, z lines with the description of the orders follow. Each consists of three integers, the j-th being uj vj bj, which signifies that bj parcels should be transported (individually) from city uj to city vj. The sum of all bj does not exceed 12.
Output
For each test case output a line with a single integer - the length of the shortest possible bicycle route for the courier.
Example
Sample input: 1 5 7 2 1 2 7 1 3 5 1 5 2 2 4 10 2 5 1 3 4 3 3 5 4 3 1 4 2 5 3 1 5 1 1 Sample output: 43
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI 3.14159265358979323846
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
const int MAXN = 1e2+5;
const int inf = 1 << 20;
int matrix[MAXN][MAXN];
int from[15], to[15];
int dp[1 << 13][105];
int solve(int mask, int prev, int p, int b){
if(mask == ((1 << p) - 1)) return dp[mask][prev] = matrix[prev][b];
if(dp[mask][prev] != -1) return dp[mask][prev];
int minn = INT_MAX;
for(int i = 0;i < p; i++){
if((mask & (1 << i)) == 0){
int x = solve( (mask | (1 << i)), to[i], p, b) + matrix[prev][from[i]] + matrix[from[i]][to[i]];
minn = min(minn, x);
}
}
dp[mask][prev] = minn;
return minn;
}
int main(){
io;
int t;
cin >> t;
while(t--){
int n, m, b;
cin >> n >> m >> b;
for(int i = 1;i <= n; i++)
for(int j = 1;j <= n; j++)
matrix[i][j] = (i == j) ? 0 : inf;
int u, v, w;
for(int i = 0;i < m; i++){
cin >> u >> v >> w;
if(u != v){
matrix[u][v] = min(matrix[u][v], w);
matrix[v][u] = min(matrix[v][u], w);
}
}
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1;j <= n; j++)
matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);
}
}
int q;
cin >> q;
int k = 0;
for(int i = 0;i < q; i++){
cin >> u >> v >> w;
for(int j = 0; j < w; j++){
from[k] = u;
to[k] = v;
k++;
}
}
memset(dp, -1, sizeof dp);
// dp[(1 << k) - 1][b]
cout << solve(0, b, k, b) << endl;
}
return 0;
}Input
5 7 2
1 2 7
1 3 5
1 5 2
2 4 10
2 5 1
3 4 3
3 5 4
3
1 4 2
5 3 1
5 1 1
Output
Demonstration
SPOJ Solution-The Courier-Solution in C, C++, Java, Python