Submission #1338556

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
long long H, W, N, a, b, c, dist[100009]; vector<pair<int, int>>X[100009], Y[100009]; vector<pair<int, int>>x[100009], y[100009];
int main() {
	cin >> H >> W >> N;
	for (int i = 0; i < N; i++) {
		cin >> a >> b >> c; X[a].push_back(make_pair(b, c)); Y[b].push_back(make_pair(a, c));
	}
	for (int i = 1; i <= H; i++) {
		sort(X[i].begin(), X[i].end());
		for (int j = 0; j < (int)X[i].size() - 1; j++) {
			x[X[i][j].first].push_back(make_pair(X[i][j + 1].first, X[i][j + 1].second - X[i][j].second));
			x[X[i][j + 1].first].push_back(make_pair(X[i][j].first, X[i][j].second - X[i][j + 1].second));
		}
	}
	for (int i = 1; i <= W; i++) {
		sort(Y[i].begin(), Y[i].end());
		for (int j = 0; j < (int)Y[i].size() - 1; j++) {
			y[Y[i][j].first].push_back(make_pair(Y[i][j + 1].first, Y[i][j + 1].second - Y[i][j].second));
			y[Y[i][j + 1].first].push_back(make_pair(Y[i][j].first, Y[i][j].second - Y[i][j + 1].second));
		}
	}
	queue<int>Q; for (int h = 1; h <= H; h++)dist[h] = (1LL << 60);
	for (int h = 1; h <= H; h++) {
		if (dist[h] != (1LL << 60))continue;
		dist[h] = 0; Q.push(h);
		while (!Q.empty()) {
			int a1 = Q.front(); Q.pop();
			for (int i = 0; i < x[a1].size(); i++) {
				if (dist[x[a1][i].first] == (1LL << 60)) {
					dist[x[a1][i].first] = dist[a1] + x[a1][i].second;
				}
				else if (dist[x[a1][i].first] != dist[a1] + x[a1][i].second) {
					cout << "No" << endl; return 0;
				}
			}
		}
	}
	for (int h = 1; h <= W; h++)dist[h] = (1LL << 60);
	for (int h = 1; h <= W; h++) {
		if (dist[h] != (1LL << 60))continue;
		dist[h] = 0; Q.push(h);
		while (!Q.empty()) {
			int a1 = Q.front(); Q.pop();
			for (int i = 0; i < y[a1].size(); i++) {
				if (dist[y[a1][i].first] == (1LL << 60)) {
					dist[y[a1][i].first] = dist[a1] + y[a1][i].second;
				}
				else if (dist[y[a1][i].first] != dist[a1] + y[a1][i].second) {
					cout << "No" << endl; return 0;
				}
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}

Submission Info

Judge Result