Problem 2191 : A Book Shop With a Frequent Greetings

Problem G: 挨拶の多い本屋さん
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2191

• 問題概要

本屋さんの入り口の位置と店員の位置が与えられている。
入り口付近の店員が一定時間かけていらっしゃいませという。
それを言い終わるのをきいている店員も反応していらっしゃいませ、という。
ただし、最後にいらっしゃいませといってから一定時間たってないといわない。

いつ、店は静かになるか?
もしくは、いつまでもいらっしゃいませ、といい続けるか。

• 解法

グラフにおとしてシュミレーション。
ループを発見するのがすこし迷った。

(いらっしゃいませというときかかる時間)*人数

くらい時間がたっても新しい店員がいらっしゃいませと言わなかったら、ループしてると判断した

正確にはどのようにループ判定をすればいいのだろう。

全員がいらっしゃいませといったのに、だれも新しく反応してないのに、とまっていない、ということでループしていることは保証されるよね?

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

using namespace std;

class Node{
public:
  int x, y;
};

bool begin(Node n1, Node n2){
  int x = abs(n1.x - n2.x), y = abs(n1.y - n2.y);
  return (x * x + y * y <= 100);
}

bool next(Node n1, Node n2){
  int x = abs(n1.x - n2.x), y = abs(n1.y - n2.y);
  return (x * x + y * y <= 2500);
}

main(){

  int d;
  cin >> d;
  rep(data, d){
    int n, time, blank;
    Node start;
    cin >> n >> time >> blank >> start.x >> start.y;
    Node node[n];
    int state[n];
    bool used[n];
 
    rep(i, n){
      cin >> node[i].x >> node[i].y;
      if(begin(start, node[i])){
	state[i] = time-1;
	used[i] = true;
      }
      else {
	state[i] = -1 - blank;
	used[i] = false;
      }
    }
    
    bool edge[n][n];
    rep(i, n){
      rep(j, n){
	if(i == j || !next(node[i], node[j])){
	  edge[i][j] = false;
	}
	else edge[i][j] = true;
      }
    }
    int cnt = 0, roop = 0;
    while(1){
      bool end = true;
      int nstate[n];
      rep(i, n)nstate[i] = state[i] - 1;
      rep(i, n){
	if(state[i] >= 0){
	  end = false;
	}
	if(state[i]  == 0){
	  rep(j, n){
	    if(!edge[i][j])continue;
	    if(state[j] >= -blank)continue;
	    nstate[j] = time-1;
	    end = false;
	    if(used[j] == false){
	      roop = 0;
	    }
	    used[j] = true;
	  }
	}
      }

      rep(i, n)state[i] = nstate[i];
      if(end)break;
      cnt++;
      if(roop >time * 1000)break;
      roop++;
    }
    if(roop > time * 1000)cout << "You're always welcome!" << endl;
    else cout << cnt << endl;
  }
}