B - 嘘つきの高橋くん | AtCoder Beginner Contest 021
B - 嘘つきの高橋くん | AtCoder Beginner Contest 021
解法
最短路の可能性があるかの判定問題．町同士の位置関係や距離(重み付け)等もないので，単に1度訪れた町をもう一度経由する(グラフとして見た時に閉路)場合は最短路ではないことはわかる．
コーナーケース検討
出発地点とゴール地点がP1，PKではないことに注意．
実装
aとbは訪れているということにしておき，PiにPi以前に訪れていた場合には最短路ではないと判定．O(K)．
int visited[101] = {};
int a, b; cin >> a >> b;
visited[a]++; visited[b]++;
int K; cin >> K;
string ans = "YES";
REP(i, K) {
int tmp; cin >> tmp;
if (visited[tmp] == 1) {
ans = "NO";
break;
}
visited[tmp]++;
}
cout << ans << endl;
データ構造・アルゴリズム
- 最短路