글 읽기 - 새로 나온 문제.

qkqhxla1 7년 전 0

시간초과가 뜨는데 알고리즘이 느려서 그런건지 아니면 반복문이 무한으로 돌아서 그런지 모르겠습니다.

맞는것같은데.. 어디서 오류가 있을까요.?

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
 
int n,m,u,v,w, k,num;
vector<pair<int ,int >> adj[100002];
    
int dfs(int u, int v, int k, int f)
{
	int visited[100001]={0,};
	visited[u] = 1;
	stack<pair<int,int>> s0;
	stack<pair<int ,vector<int>>> s1;
	s0.push(make_pair(u,0));
	vector<int> t;
	t.push_back(u);
	s1.push(make_pair(0,t));
	while(!s0.empty())
	{
		int p[3];
		vector<int> p3;
		p[0] = s0.top().first;
		p[1] = s0.top().second;
		p[2] = s1.top().first;
		p3 = s1.top().second;
		//cout<<p[0]<<" "<<p[1]<<" "<<p[2]<<" ";
		//for(int i=0;i<p3.size();i++)
		//	cout<<"pp = "<<p3[i]<<endl;
		s0.pop(); s1.pop();
		if(f==0 && p[0]==v)
			return p[1];
		else if(f==1 && p[2]==k)
			return p3[k-1];
		for(auto& t: adj[p[0]])
		{
			if(visited[t.first]==0)
			{
				p3.push_back(t.first);
				s0.push(make_pair(t.first, t.second+p[1]));
				s1.push(make_pair(p[2]+1, p3));
				visited[t.first] = 1;
				p3.pop_back();
			}
		}
	}
}
    
int main()
{
    cin>>n;
	for(int i=0;i<n-1;i++)
	{
		scanf("%d %d %d",&u,&v,&w);
		adj[u].push_back(make_pair(v,w));
		adj[v].push_back(make_pair(u,w));
	}
	cin>>m;
	for(int i=0;i<m;i++)
	{
		scanf("%d",&num);
		if(num==1)
		{
			scanf("%d %d",&u,&v);
			printf("%d\n",dfs(u,v,0,0));
		}
		else
		{
			scanf("%d %d %d",&u,&v,&k);
			printf("%d\n",dfs(u,v,k,1));
		}
	}
    return 0;
}

jongseo_park 4년 전 0

이거 아마 dfs가 아니라 LDS(최소공통부모) 알고리즘으로 풀어야 할 겁니다...

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

문제

문제

출처

ICPC

새로 나온 문제.

qkqhxla1 7년 전 0

jongseo_park 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말