Problem: manicmoving (2017 round1)

Thanks to his tireless hard work, Wilson has been promoted and now gets to
drive his moving company's trucks! No, he can't believe it either.

The moving company services a region that has **N** towns, with **M** roads
running amongst them. The _i_th road connects two different towns **Ai** and
**Bi**, requires **Gi** litres of gas to drive along, and can be traversed in
either direction. There may be multiple roads running directly between any
given pair of towns.

Today, Wilson has been scheduled to transport **K** families' belongings. The
_i_th family is moving from town **Si** to a different town **Di**. Wilson and
his truck will be starting off the day at the company headquarters in town 1.
For each family, he'll need to drive to their starting town by following a
sequence of roads, load his truck there, and at some point later, arrive at
their destination town to unload their belongings. His truck is large enough
to fit at most 2 families' sets of belongings at a time, meaning that he
doesn't necessarily need to deliver each load immediately after picking it up.

However, Wilson has been instructed that the **K** families must be helped
strictly in order. In particular, if i < j, then the _i_th family's belongings
must be loaded before the _j_th family's belongings are loaded, and the _i_th
family's belongings must be delivered before the _j_th family's belongings are
delivered.

Although Wilson's wages are higher than ever, he does have to pay for the
truck's gas out of his own pocket, so it's in his best interest to get the job
done while burning through as little of it as possible. Of course, he'll still
need to be careful to follow his company's strict rules regarding the relative
order of the families' loads and unloads, to avoid getting fired. That being
said, it's a possibility for it to be impossible to even complete all of the
requested moves, in which case Wilson will simply call it a day and stay home
instead.

### Input

Input begins with an integer **T**, the number of sets of families Wilson
needs to move.

For each case, there is first a line containing three space-separated
integers, **N**, **M**, and **K**.

Then, **M** lines follow, the _i_th of which contains 3 space-separated
integers, **Ai**, **Bi**, and **Gi**.

Then, **K** lines follow, the _i_th of which contains 2 space-separated
integers, **Si** and **Di**.

### Output

For the _i_th case, print a line containing "Case #**i**: " followed by the
minimum amount of gas required for Wilson to validly complete his delivery
schedule, or -1 if it can't be done.

### Constraints

1 ≤ **T** ≤ 100  
2 ≤ **N** ≤ 100  
1 ≤ **M** ≤ 5,000  
1 ≤ **K** ≤ 5,000  
1 ≤ **Ai**, **Bi** ≤ **N**, **Ai** ≠ **Bi**  
1 ≤ **Si**, **Di** ≤ **N**, **Si** ≠ **Di**  
1 ≤ **Gi** ≤ 1,000  

### Explanation of Sample

In the first case, Wilson drives to town 2, and then drives the first family's
belongings back to town 1. That's 8 litres gas so far. Then Wilson drives to
city 3 (11 more litres of gas), picks up the remaining belongings, and drives
them all to town 2 (7 litres of gas). A grand total of 8 + 11 + 7 = 26 litres
of gas.

In the fourth case, Wilson can't reach town 4 in order to complete the 2nd and
3rd families' moves.



Sample input:
5
3 2 3
1 2 4
2 3 7
2 1
3 2
3 2
3 2 3
1 2 4
2 3 7
3 2
2 1
3 2
4 4 4
1 2 3
1 3 1
2 4 10
3 4 1
1 2
2 4
4 1
3 1
4 2 4
1 2 3
1 3 1
1 2
2 4
4 1
3 1
7 8 10
7 5 9
1 2 14
3 7 7
2 5 8
4 3 10
1 4 3
7 3 5
4 2 16
3 2
5 1
7 3
5 3
1 7
3 2
1 5
4 7
7 2
5 1


Sample output:
Case #1: 26
Case #2: 40
Case #3: 10
Case #4: -1
Case #5: 219



Code: // Hacker Cup 2017
// Round 1
// Manic Moving
// Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=getchar();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

int main()
{
	int T,t;
	int N,M,K;
	int i,j,k,d,ans;
	int A[5000],B[5000];
	static int dist[100][100],dyn[5001][101][2];
	Read(T);
		Fox1(t,T)
		{
			Read(N),Read(M),Read(K);
			Fill(dist,60);
				Fox(i,N)
					dist[i][i]=0;
				while (M--)
				{
					Read(i),Read(j),Read(k),i--,j--;
					Min(dist[i][j],k);
					Min(dist[j][i],k);
				}
				Fox(i,N)
					Fox(j,N)
						Fox(k,N)
							Min(dist[j][k],dist[j][i]+dist[i][k]);
				Fox(i,K)
					Read(A[i]),Read(B[i]),A[i]--,B[i]--;
				Fox(i,K)
					if (max(dist[0][A[i]],dist[0][B[i]])>INF)
					{
						ans=-1;
						goto Done;
					}
			Fill(dyn,60);
			dyn[0][0][0]=0;
				Fox(i,K)
					Fox(k,2)
						Fox(j,N)
							if ((d=dyn[i][j][k])<INF)
								if (!k) // must pick up i next
									Min(dyn[i][A[i]][1],d+dist[j][A[i]]);
								else // i already picked up
								{
									// deliver i immediately
									Min(dyn[i+1][B[i]][0],d+dist[j][B[i]]);
									// pick up i+1 and then deliver i
										if (i<K-1)
											Min(dyn[i+1][B[i]][1],d+dist[j][A[i+1]]+dist[A[i+1]][B[i]]);
								}
			ans=dyn[K][B[K-1]][0];
Done:;
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}