글 읽기 - 도와주세요 고수님들 시간초과 질문...ㅠ

vhxpffltm12 6년 전 0

큐를 사용해서 bfs방식으로 접근을 했는데 시간초과가 뜨네요 ㅠ

다른방법을 사용해야ㅕ 하나요??

#include <stdio.h>
#include<stdlib.h>
#include<string.h>
#include <iostream>
#include<string>
#include<vector>
#include<queue>
#include<math.h>
#include<algorithm>
#include<stack>
using namespace std;

int main()
{
	int n,m;
	vector<int> arr[50000];
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		arr[a].push_back(b);
		arr[b].push_back(a);
	}
	cin >> m;
	for (int z = 0; z < m; z++) {
		int visit[50000] = { 0 }, visit2[50000] = { 0 }, kkk = 987654321, kk = 0;
		int ans[50000] = { 0 }, ans2[50000] = { 0 }, chk = 1, chk2 = 1;
		queue<int> q, q2;
		int a, b;
		scanf("%d %d", &a, &b);
		q.push(a);
		q2.push(b);
		visit[a] = 1;
		visit2[b] = 1;

		while (!q.empty()) {
			int x;
			x = q.front();
			q.pop();
			for (int i = 0; i < arr[x].size(); i++) {
				if (visit[arr[x][i]] == 0) {
					visit[arr[x][i]] = 1;
					q.push(arr[x][i]);
					ans[arr[x][i]] = chk;
				}
			}
			chk++;
		}
		
		while (!q2.empty()) {
			int x;
			x = q2.front();
			q2.pop();
			for (int i = 0; i < arr[x].size(); i++) {
				if (visit2[arr[x][i]] == 0) {
					visit2[arr[x][i]] = 1;
					q2.push(arr[x][i]);
					ans2[arr[x][i]] = chk2;
				}
			}
			chk2++;
		}
		for (int i = 1; i <= n; i++) {
			if (ans[i] != 0 || ans2[i] != 0) {
				if (ans[i] + ans2[i] < kkk) {
					kkk = ans[i] + ans2[i];
					kk = i;
				}
			}
		}
		printf("%d\n", kk);

	}
	return 0;
}

chogahui05 6년 전 0

한 개의 쿼리당 수행하는 시간복잡도가 얼마인지 아신다면

왜 시간초과가 나시는 지 아실 거 같네요.

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

문제

문제

출처

ICPC

도와주세요 고수님들 시간초과 질문...ㅠ

vhxpffltm12 6년 전 0

chogahui05 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말