글 읽기 - 수행시간에 대해 문의드립니다.

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cstring>
#include<queue>
#include <chrono>
using namespace std;
using namespace chrono;
bool prime[10000];

vector<string> v;

int bfs(int a, int b) {
	queue<int> q;
	bool visit[10000] = { false, };
	int dist[10000] = { 0, };
	q.push(a);
	dist[a] = 0;
	visit[a] = true;
	while (!q.empty()) {
		int t = q.front();
		string front = to_string(t);
		q.pop();
		if (t == b) return dist[t];
		int size = v.size();
		for (int i = 0; i < size; i++) {
			string x = v[i];
			int k = stoi(x);
			if (visit[k]) continue;
			int c = 0;
			for (int j = 0; j < 4; j++) {
				if (front[j] != x[j]) c++;
			}
			if (c != 1) continue;
			dist[k] = dist[t] + 1;
			visit[k] = true;
			q.push(k);
		}
	}
	return -1;
}

void f() {
	for (int i = 2; i <= 9999; i++) {
		if (prime[i]) continue;
		if (i >= 1000) v.push_back(to_string(i));
		for (int j = i*i; j <= 9999; j += i) {
			prime[j] = true;
		}
	}
	sort(v.begin(), v.end());
}

int main() {
	system_clock::time_point start = system_clock::now();
	ios_base::sync_with_stdio(false);
	f();
	int T;
	cin >> T;
	while (T--) {
		int a, b;
		cin >> a >> b;
		int ans = bfs(a, b);
		if (ans != -1) cout << ans << endl;
		else cout << "Impossible" << endl;
	}
	system_clock::time_point end = system_clock::now();
	microseconds microSec = duration_cast<microseconds>(end - start);
	cout << microSec.count() << " us\n";
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

수행시간에 대해 문의드립니다.

unilep 6년 전 0

sgchoi5 6년 전 1

unilep 6년 전 0

sgchoi5 6년 전 0

unilep 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말