学步园

题目大意就是，有一个图，上面有一些顶点，代表一些城市，在某些时刻， 某个城市里会有人需要礼物， 哈利波特需要及时的将礼物送到，但是哈利每1秒只能走一个单位长度，所以他需要朋友的帮助，来使所有的人都能及时的收到礼物。问需要的最少的朋友个数。

那么看完题目后，实际上可以发现其跟路径覆盖非常有关系，因为是一些人走一些路径来将礼物送到。

所以要先将任意两点间的最短路求好。然后枚举任意两个任务，如果两点间的距离小于两点间的时间差，当然，这个时间差是有先后顺序的，这两个任务就可以进行连边，就这样，到最后可以发现是经典的最小路径覆盖模型。

/*
ID: CUGB-wwj
PROG:
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 1000000000
#define MAXN 1005
#define PI acos(-1.0)
using namespace std;
struct node
{
    int v, next;
}edge[MAXN * MAXN];
int e, head[MAXN], mark[MAXN], cx[MAXN], cy[MAXN], n;
int d[MAXN][MAXN];
int m, q;
int need[MAXN], ti[MAXN];
void insert(int x, int y)
{
    edge[e].v = y;
    edge[e].next = head[x];
    head[x] = e++;
}
int path(int u)
{
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].v;
        if(!mark[v])
        {
            mark[v] = 1;
            if(cy[v] == -1 || path(cy[v]))
            {
                cx[u] = v;
                cy[v] = u;
                return 1;
            }
        }
    }
    return 0;
}
int solve()
{
    int ans = 0;
    memset(cx, -1, sizeof(cx));
    memset(cy, -1, sizeof(cy));
    for(int i = 1; i <= n; i++)
    {
        memset(mark, 0, sizeof(mark));
        ans += path(i);
    }
    return ans;
}

int main()
{
    int T, x, y, z;
    scanf("%d", &T);
    int cas = 0;
    while(T--)
    {
        e = 0;
        memset(head, -1, sizeof(head));
        scanf("%d%d%d", &n, &m, &q);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
             {
                 d[i][j] = INF;
                 if(i == j) d[i][j] = 0;
             }
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d%d", &x, &y, &z);
            x ++; y ++;
            d[x][y] = d[y][x] = min(d[x][y], z);
        }
        for(int k = 1; k <= n; k++)
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                {
                    if(d[i][k] + d[k][j] < d[i][j])
                    d[i][j]  = d[i][k] + d[k][j];
                }
        for(int i = 0; i < q; i++)
        {
            scanf("%d%d", &need[i], &ti[i]);
            need[i]++;
        }
        for(int i = 0; i < q; i++)
            for(int j = 0; j < q; j++)
            {
                if(i == j) continue;
                if(d[need[i]][need[j]] <= ti[j] - ti[i])
                    insert(i + 1, j + 1);
            }
        n = q;
        printf("Case %d: ", ++cas);
        printf("%d\n", n - solve() - 1);
    }
    return 0;
}