Language: C++

#include <cstdio>
#include<string>
#include<algorithm>
#define max_n 100
#define max_m 1000
#define max_l 1000
//#define MIN(a,b)  ( ((a)<(b) ) ? (a) : (b) )
inline int min(int x, int y){
  return (x<y)? x:y;
}

using namespace std;

class Req{
public:
  char house;
  int time;
};

class LessReq {
public:
    bool operator()(const Req& x, const Req& y) const {
        return x.time < y.time; 
    }
};
int n,m,l;
//char graph[max_n][max_n];
int dist[max_n][max_n];
//char req_house[max_l];
//int req_time[max_l];
Req reqs[max_l];
//リクエストx配送後に、リクエストy配送可能かを示す有向グラフ（DAG）
//bool req_graph[max_l][max_l];
int req_graph[max_l][max_l+1];
int num_child[max_l];//各リクエストxの子の数
int pathParent[max_l]; //被覆パスにおけるリクエストxの親
int searched1[max_l];
int searched2[max_l]; 

//デバグ用 設定表示関数
void print_setting(){
  int i,j;
  printf("(n,m,l)=(%3d,%3d,%3d)\n",n,m,l);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      printf("%4d",dist[i][j]);
    }
    printf("\n");
  }
  printf("\n");
  for(i=0;i<l;i++){
    printf("%4d%4d\n",reqs[i].house,reqs[i].time);
  }
  printf("\n");
  for(i=0;i<l;i++){
    printf("%4d: ",i);
    for(j=0;j<num_child[i];j++){
      printf("%4d",req_graph[i][j]);
    }
    printf("\n");
  }
  printf("\n");
}

//すべての宅間の最短距離を算出、distに記録
void compute_dist(){
  register int i,j,k;
  
  for(i=0;i<n;i++) dist[i][i] = 0;
  /*
  for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++){
    if(dist[i][k] < 0) continue;
    if(dist[k][j] < 0) continue;
    if(dist[i][j] < 0) dist[i][j] = dist[i][k]+dist[k][j];
    else dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
  }
   */
  for(k=0;k<n;k++){
    for(i=0;i<k;i++){
      for(j=i+1;j<k;j++){  //i<j<k
        if(dist[i][k] < 0) continue;
        if(dist[j][k] < 0) continue;
        if(dist[i][j] < 0) dist[i][j] = dist[i][k]+dist[j][k];
        else dist[i][j] = min(dist[i][j],dist[i][k]+dist[j][k]);
      }
      for(j=k+1;j<n;j++){  //i<k<j
        if(dist[i][k] < 0) continue;
        if(dist[k][j] < 0) continue;
        if(dist[i][j] < 0) dist[i][j] = dist[i][k]+dist[k][j];
        else dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
      }
    }
    for(i=k+1;i<n;i++){
      for(j=i+1;j<n;j++){  //k<i<j
        if(dist[k][i] < 0) continue;
        if(dist[k][j] < 0) continue;
        if(dist[i][j] < 0) dist[i][j] = dist[k][i]+dist[k][j];
        else dist[i][j] = min(dist[i][j],dist[k][i]+dist[k][j]);
      }      
    }
  }
  for(i=0;i<n;i++)for(j=i+1;j<n;j++){
    dist[j][i] = dist[i][j];
  }
}
//req_graphの構成
void compute_req_graph(){
  int i,j;
  int h1,h2,t1,t2;

  memset(num_child,0,l*sizeof(int));
  for(i=0;i<l;i++){    
    for(j=i+1;j<l;j++){
      h1 = reqs[i].house; h2 = reqs[j].house;      
      if((dist[h1][h2] >= 0)
         && (dist[h1][h2] <= reqs[j].time - reqs[i].time)){
        req_graph[i][num_child[i]++] = j;
      }      
      /*
      if((dist[h1][h2] >= 0) && (dist[h1][h2] <= t2 - t1)){
        req_graph[i][j] = true;
        num_child[i]++;
      }
      else
        req_graph[i][j] = false;
      */      
    }
  }
}

int find(int i){
  int child, x, found;
  static bool on_find[max_l];
  static bool firstInvocation = true;
  
  if(firstInvocation){
    memset(on_find,0,sizeof(on_find));
    firstInvocation = false;
  }

  /*
  printf("%d: ",i);
  for(int j=0;j<l;j++) printf("%d",on_find[j]);
  printf("\n");
  */
  
  //親権の空いている子を探す
  for(int j=searched1[i]+1;j<num_child[i];j++){
    child = req_graph[i][j];
    if(pathParent[child] >= 0) continue;
    pathParent[child] = i; //childを自分の子とする
    searched1[i] = j; //探索点を記憶
    return child;    
  }
  searched1[i] = num_child[i];
  //printf("%d: search1 failed\n",i);
  
  //他の親から親権を譲ってもらえる子を探す
  on_find[i] = true;
  for(int j=searched2[i]+1;j<num_child[i];j++){
    child = req_graph[i][j];
    x = pathParent[child]; //x: childのパス上の親
    if(on_find[x]) continue; //閉路検出
    //printf("%d: %d has child of id %d\n",i,x,child);
    found = find(x); //xにchildの親権を譲ってもらう
    if(found < 0) continue;
    pathParent[child] = i; //xからchildの親権をもらう
    searched2[i] = j; //探索点を記憶
    on_find[i] = false;
    return child;
  }
  on_find[i] = false;
  searched2[i] = num_child[i];
  //printf("%d: search2 failed\n",i);
  return -1; //リクエストiはどの子の親権も獲得できず
}

//req_graphのパス被覆を求め、被覆数を返す。
int num_covers(){
  int num=0;
  
  memset(pathParent,-1,l*sizeof(int));
  memset(searched1,-1,l*sizeof(int));
  memset(searched2,-1,l*sizeof(int));
  for(int i=0;i<l;i++){
    if(pathParent[i]<0) num++;
    //    printf("(i,num) = (%4d,%4d)\n",i,num);
    find(i);
  }
  return num;
}

//以下、ひとつの問題例を解くsantas関数
//プレゼント配送に必要なサンタの数を出力
int santas(){
  int u,v,d;
  int i;

  //入力読み込み
  memset(dist,-1,sizeof(dist));
  for(i=0;i<m;i++){
    scanf("%d%d%d",&u,&v,&d);
    dist[u][v] = d;
  }
  for(i=0;i<l;i++){
    scanf("%d%d",&(reqs[i].house),&(reqs[i].time));
  }
  compute_dist();//すべてのhouse間の最短距離を算出、distに記録
  sort(reqs,reqs+l,LessReq());
  compute_req_graph();//req_graphの構成
  //print_setting();//設定表示  
  return num_covers();
}



//以下メイン関数
int main(){
  while(1){
    scanf("%d%d%d",&n,&m,&l);
    if(n == 0) break;
    printf("%d\n",santas());
  }
  return 0;
}

Compiler output:
a.cc: In function 'void compute_dist()':
a.cc:67:16: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   67 |   register int i,j,k;
      |                ^
a.cc:67:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   67 |   register int i,j,k;
      |                  ^
a.cc:67:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   67 |   register int i,j,k;
      |                    ^
a.cc: In function 'void compute_req_graph()':
a.cc:111:3: error: 'memset' was not declared in this scope
  111 |   memset(num_child,0,l*sizeof(int));
      |   ^~~~~~
a.cc:4:1: note: 'memset' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
    3 | #include<algorithm>
  +++ |+#include <cstring>
    4 | #define max_n 100
a.cc: In function 'int find(int)':
a.cc:137:5: error: 'memset' was not declared in this scope
  137 |     memset(on_find,0,sizeof(on_find));
      |     ^~~~~~
a.cc:137:5: note: 'memset' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
a.cc: In function 'int num_covers()':
a.cc:182:3: error: 'memset' was not declared in this scope
  182 |   memset(pathParent,-1,l*sizeof(int));
      |   ^~~~~~
a.cc:182:3: note: 'memset' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
a.cc: In function 'int santas()':
a.cc:200:3: error: 'memset' was not declared in this scope
  200 |   memset(dist,-1,sizeof(dist));
      |   ^~~~~~
a.cc:200:3: note: 'memset' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'