AOJ 2251 : Merry Christmas

問題リンク：Merry Christmas | Aizu Online Judge

解法：
二部グラフにおとしてマッチングをした
二部グラフにする際にリクエストをノードとした
エッジをつなぐ前に、家と家の最短距離をフロイドワーシャルで求め、
(リクエストiが終わる時間)+(リクエストiの家からリクエストjの家までの最短距離) <= (リクエストjの時間)　が満たされるならはリクエストiからリクエストjに辺をつないだ

そして(リクエストの数)-(最大流の結果)とした

リクエスト間の関係を有向グラフで表すとDAGになっている
これを最小のパス数で全てのノードをカバーすることは、最小のサンタ数で全てのリクエストを行うことと同じになる
パスの始点でないノードは別のノードから訪れられている
つまりその様に別のノードから訪れられているノードの数を最大化すればよい
最大流の結果は、上の説明でいう別のノードから訪れられているノードの数に等しいので、リクエストの数からこの結果を引くことでパスの始点（サンタの数）の数がわかる

コード：

//max_flowは蟻本のものがそのまんまなので略
int N,M,L;
int mincost[MAX][MAX];
vector<ii> ps;

int main()
{
  while(cin >> N >> M >> L,N|M|L)
    {
      rep(i,MAX)G[i].clear();
      rep(i,N)rep(j,N)mincost[j][i] = inf;
      rep(i,N)        mincost[i][i] = 0;

      	int u,v,d;
	rep(i,M)
	  {
	    cin >> u >> v >> d;
	    mincost[u][v] = mincost[v][u] = d;
	  }
	rep(i,N)rep(j,N)rep(k,N)mincost[j][k] = min(mincost[j][k],mincost[j][i]+mincost[i][k]);

	ps.clear();
	ps.resize(L);
	rep(i,L)cin >> ps[i].first >> ps[i].second;
	V = L;

	int st = 2*V,ed = 2*V+1;
	rep(i,V)        add_edge(st,i,1);
	rep(i,V)rep(j,V)if(i != j && ps[i].second+mincost[ps[i].first][ps[j].first] <= ps[j].second)add_edge(i,V+j,1);
	rep(i,V)        add_edge(V+i,ed,1);

	cout << V-max_flow(st,ed) << endl;

      }

    
  return 0;
}