Livearchive 5906 Smoking gun

問題

n人の人が平面上にいて、それぞれの座標が与えられる。
これらの人が、合計でm個、次のような目撃証言をした。
「私は、a[i]がb[i]よりも先に銃を撃つのを聞いた」

音の進む速さは有限であるので、
先に銃を撃つ音が聞こえた者が、先に発砲したとは限らない。

このとき、発砲した人の順序が、矛盾しているならIMOPSSIBLEを、
一意に定まるならばその順序を、そうでなければ、UNKNOWNを出力せよ。

制約条件

n≦100
m≦1000

方針

人kが、jより先にiが発砲したと証言したとき、
d(k, i)をd1, d(k, j)をd2とすれば、
iの発砲時刻＜jの発砲時刻 + d2 - d1という不等式が立つ。

それぞれの証言は、一つの不等式制約になる。
不等式制約の双対を取ると、最短路問題になる（蟻本の牛の距離の問題のやつ）ので、
最短路問題にして考える。

t[i] < t[j] + xが成り立つとき、
jからiに、コストxの辺を張ればいい。
そして、グラフに非負の閉路があれば矛盾である。

グラフを作り終えたら、ワーシャルフロイドをして、全点間の最短距離を求める。
ここから、一番最初に発砲した人を決定していけばいい。
一番最初に発砲した人は、
全てのjについて、d[j][i] < 0となる人iである。

なぜなら、d[j][i] < 0のとき、i < j - xとなっているはずだから。
iがわかったら、iを取り除いて同様に考える。
iが一意に定まらなかったら、UNKOWN.

ソースコード

int n, m;
string name[100];
double x[100], y[100], d[100][100];
bool use[100];

inline double dist(int a, int b){
	double d2 = (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]);
	return sqrt(d2);
}

int main()
{
	int cs;
	cin >> cs;
	while(cs--){
		cin >> n >> m;
		map<string, int> id;
		rep(i, n){
			cin >> name[i] >> x[i] >> y[i];
			id[name[i]] = i;
			use[i] = 0;
		}
		
		rep(i, n) rep(j, n) d[i][j] =  INF;
		
		rep(i, m){
			string a, tmp, c, f;
			cin >> a >> tmp >> c >> tmp >> tmp >> f;
			
			int p = id[a], q = id[c], r = id[f];
			double d1 = dist(p, q), d2 = dist(p, r);
			d[r][q] = min(d[r][q], d2 - d1);
			
			use[q] = use[r] = 1;
		}
		
		rep(k, n) rep(i, n) if(use[i]) rep(j, n) if(use[j])
			d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
		
		bool end = 0;
		rep(i, n) if(use[i] && d[i][i] < EPS){
			cout << "IMPOSSIBLE" << endl;
			end = 1;
			break;
		}
		if(end) continue;
		
		int k = 0;
		rep(i, n) if(use[i]) k++;
		
		vi ord;
		rep(it, k){
			int mn = -1;
			rep(i, n) if(use[i]){
				bool ok = 1;
				rep(j, n) if(i != j && use[j] && d[j][i] > EPS) ok = 0;
				if(ok) mn = i;
			}
			
			if(mn < 0){
				cout << "UNKNOWN" << endl;
				goto END;
			}
			ord.pb(mn);
			use[mn] = 0;
		}
		rep(i, k) cout << name[ord[i]] << (i == k - 1 ? "\n" : " ");
		
		END:;
	}
	return 0;
}