PKU 1338 Ugly Numbers

• 最短経路問題として解いた
• 各ノードを数字、各エッジをx2,x3,x5に対応させる
• 小さな数字から順に展開していく

int main() {
	set<ll> q;
	q.insert(1);
	vector<int> answer;
	while (answer.size() < 1500) {
		const ll value = *q.begin();
		q.erase(q.begin());
		answer.push_back(value);

		q.insert(value * 2);
		q.insert(value * 3);
		q.insert(value * 5);
	}

	for (int n; cin >> n && n; ) {
		cout << answer[n - 1] << endl;
	}
}