AOJ : 2191 - 挨拶の多い本屋さん (A Book Shop With a Frequent Greetings)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2191&lang=jp
日本語なので, 説明省略.

アルゴリズム

始点から順番にシミュレートして, ある程度時間がたっても鳴り止まないようなら, ループを中断する.
↑ある程度っていうのは, 僕もはっきりわからないので, 1000回程度挨拶したら, 中断するようにしてます.

プログラム

int tm[1000];
int x[1000],y[1000];

int main(void){
  int n;
  cin>>n;

  while(n--){
    int N,X,Y;
    double sx,sy;
    cin>>N>>X>>Y>>sx>>sy;

    for(int i=0;i<N;i++) cin>>x[i]>>y[i];

    vector<int> t[N];
    for(int i=0;i<N-1;i++){
      for(int j=i+1;j<N;j++){
        if((x[j]-x[i])*(x[j]-x[i]) + (y[j]-y[i])*(y[j]-y[i]) <= 2500){
          t[i].push_back(j);
          t[j].push_back(i);
        }
      }
    }
    vector<int> v;
    for(int i=0;i<N;i++) tm[i] = -999999999;

    int ans = 0;
    for(int i=0;i<N;i++){
      if((sx-x[i])*(sx-x[i]) + (sy-y[i])*(sy-y[i]) <= 100){
        v.push_back(i);
        ans = tm[i] = X;
      }
    }

    int loop = 10000;
    while(!v.empty() && loop>0){
      vector<int> nv;
      for(int i=0;i<v.size();i++){
        int from = v[i];
        for(int j=0;j<t[from].size();j++){
          int to = t[from][j];

          if(tm[from] - Y > tm[to]){
            nv.push_back(to);
            ans = tm[to] = tm[from] + X;
          }
        }
      }

      v = nv;
      loop--;
    }

    if(loop == 0)
      cout<<"You're always welcome!\n";
    else
      cout<<ans<<endl;
  }

  return 0;
}