Gym 101673E Is-A? Has-A? Who Knowz-A?

题目：传送门

题意：有n个关系，有m个询问，关系有a is  b，a has b  注意（a is b！=b is a），然后 is和has都具有传递性。

每次询问问你a，b的关系是否正确

思路：根据is关系和has关系建边，如果是is关系，那么两个点之间的边都是is边，如果是has关系，两个点之间的路径就会存在至少一个has，这样用dfs或者最短路都可以解决。

附上代码：

#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
map<string, int>p;
typedef long long ll;
#define inf 0x3f3f3f3f
int gx[510][510];
int hh[510][510];
int cnt = 1;
void flod() {
	for (int i = 1; i < cnt; i++) {
		for (int z = 1; z < cnt; z++) {
			for (int k = 1; k < cnt; k++) {
				if (gx[z][i]<inf&&gx[i][k]<inf)
					gx[z][k] = min(gx[z][k], gx[z][i] + gx[i][k]);
				if (hh[z][i]<inf&&hh[i][k]<inf)
					hh[z][k] = min(hh[z][k],hh[z][i] + hh[i][k]);
				if (hh[z][k] < 0) hh[z][k] = -1;
			}
		}
	}
}
int main(void) {
	int n, m;
	p.clear();
	for (int i = 0; i < 510; i++) {
		for (int z = 0; z < 510; z++) {
			if (i == z) gx[i][z] = 0;
			else gx[i][z] = gx[z][i] = inf;
		}
	}
	for (int i = 0; i < 510; i++) {
		for (int z = 0; z < 510; z++) {
			if (i == z) hh[i][z] = 0;
			else hh[i][z] = hh[z][i] = inf;
		}
	}
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string a, b, c;
		cin >> a >> b >> c;
		int x1, x2;
		if (p[a] == 0) {
			p[a] = cnt++;
		}
		if (p[c] == 0) {
			p[c] = cnt++;
		}
		x1 = p[a];
		x2 = p[c];
		if (b[0] == 'i') {
			gx[x1][x2] = 0;
			hh[x1][x2] = min(hh[x1][x2],0);//这里是个bug
		}
		else if (b[0] == 'h') {
			hh[x1][x2] = -1;
		}
	}
	flod();
	for (int i = 0; i < m; i++) {
		string a, b, c;
		cin >> a >> b >> c;
		cout << "Query " << i + 1 << ": ";
		if (b[0] == 'i') {
			if (gx[p[a]][p[c]] == 0) {
				cout << "true" << endl;
			}
			else cout << "false" << endl;
		}
		else if (b[0] == 'h') {
			if (hh[p[a]][p[c]] < 0) {
				cout << "true" << endl;
			}
			else cout << "false" << endl;
		}
	}
	return 0;
}