aoj 2251 2 분 그림 일치

제목 링크:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2251
제목: 최소한 산타클로스 몇 명 에 게 선물 을 주 라 고 한다.약간의 점 을 주 었 는데, 그 사이 에 약간의 경로 가 존재 한다.일정한 시간 에 산 타 할아버지 가 도착 해 야 한 다 는 점 을 제시 했다. 산 타 할 아버 지 는 어느 시점 에서 든 출발 할 수 있다.최소한 의 산타클로스 개 수 를 구하 다.
사고: 그림 을 만 드 는 것 이 매우 시 크 하고 본인 이 너무 어 리 석 어서 정말 알 아 보지 못 했다.최 악의 경우 점 마다 산 타 할아버지 가 필요 해 인원 을 줄 이 는 방법 을 고려 해 야 한다.도착 해 야 할 모든 점 에 대해 서 는 도착 후 정 해진 시간 내 에 다른 점 으로 갈 수 있 는 지 를 고려 해 가능 하 다 면 이 두 점 을 연결 해 야 한다.이 두 가지 점 은 산 타 할아버지 한 명 만 필요 하 다 는 뜻 이다.그렇다면 이때 가장 큰 매 칭 수 는 절약 할 수 있 는 산 타 할아버지 이 고 가장 작은 사 이 드 커버 는 필요 한 가장 적은 산 타 할아버지 의 개수 이다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define M 20009
const int INF = 0x3f3f3f3f;
typedef pair<int,int> pii;
int n,m,l;
int dis[M][M];
bool used[M];
int match[M];
vector<int> G[M];
vector<pii> qu;
void init()
{
    qu.clear();
    for(int i = 0;i < 2*n;i++)
    {
        for(int j = 0;j < 2*n;j++)
        {
            if(i == j) dis[i][j] = 0;
            else dis[i][j] = INF;
        }
    }
    for(int i = 0;i < M;i++) G[i].clear();
}
void add_edge(int u,int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}
void floyd()
{
    for(int k = 0; k < n;k++)
    {
        for(int i = 0;i < n;i++)
        {
            for(int j = 0;j < n;j++)
                dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
        }
    }
}
void build()
{
    for(int i = 0;i < qu.size();i++)
    {
        for(int j = 0;j < qu.size();j++)
        {
            if(i == j) continue;
            pii a = qu[i], b = qu[j];
            int tmp = b.second - a.second;
            if(tmp >= dis[a.first][b.first])
            {
                add_edge(i,j+l);
            }
        }
    }
}
bool dfs(int u)
{
    for(int i = 0;i < G[u].size();i++)
    {
        int v = G[u][i];
        if(!used[v])
        {
            used[v] = true;
            if(match[v] < 0 || dfs(match[v]))
            {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}
int hungry()
{
    int res = 0;
    memset(match,-1,sizeof(match));
    for(int i = 0 ;i < l;i++)
    {
        memset(used,false,sizeof(used));
        if(dfs(i)) res++;
    }
    return res;
}
int main()
{
    while(scanf("%d %d %d",&n,&m,&l) == 3)
    {
        init();
        if(n == 0 && m == 0 && l == 0) break;
        for(int i = 0;i < m;i++)
        {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            dis[a][b] = c;
            dis[b][a] = c;
        }
        for(int i = 0;i < l;i++)
        {
            int a,b;
            scanf("%d %d",&a,&b);
            qu.push_back(make_pair(a,b));
        }
        floyd();
        /*for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) printf("%d ",dis[i][j]); printf("
"); }*/
        build();
        int tmp = hungry();
        //printf("debug -- tmp = %d
",tmp);
        printf("%d
",l - hungry());
    }
    return 0;
}