글 읽기 - 시간초과 질문합니다

john6014 6년 전 0

prim 알고리즘을 최소힙을 같이 사용해서 해결하려고 했는데.. 아무래도 문자열이다보니 저걸 탐색하는 과정에서 시간을 많이 잡아먹는건지 아니면 prim + 최소힙을 써도 시간내에 해결못하는건지 알고 싶습니다. 문자열을 정수로 매칭하는것도 어떻게 해야할지 생각이 안나서 질문합니다.

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <string>
#include <functional>
#pragma warning(disable:4996)
using namespace std;

pair<int, int> Name(vector<string> &name, char str1[], char str2[]);

int main()
{
	char str1[21], str2[21];
	int cnt, size, N, T;
	scanf("%d", &T);

	for (int i = 0; i < T; i++)
	{
		priority_queue<pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > q;
		vector<string> name;
		vector< vector< pair<int, int> > > G(100000);

		scanf("%d", &N);
		for (int j = 0; j < N; j++)
		{
			cnt = 0;
			scanf("%s%s", str1, str2);

			auto p = Name(name, str1, str2);
			vector<bool> Check(name.size(), false);
			

			G[p.first].push_back(make_pair(p.second, 1));
			G[p.second].push_back(make_pair(p.first, 1));

			size = G[p.first].size();
			for (int k = 0; k < size; k++)
				q.push(make_pair(G[p.first][k].second, G[p.first][k].first));

			Check[p.first] = true;
			while (q.empty() != 1)
			{
				int Ftemp = q.top().first, Stemp = q.top().second;
				q.pop();

				if (Check[Stemp] == false)
				{
					cnt++;
					Check[Stemp] = true;

					for (int k = 0; k < G[Stemp].size(); k++)
						if(Check[G[Stemp][k].first] == false)
							q.push(make_pair(G[Stemp][k].second, G[Stemp][k].first));
				}
			}
			
			printf("%d\n", cnt + 1);
		}
	}
	return 0;
}

pair<int, int> Name(vector<string> &name, char str1[], char str2[])
{
	int a, b, flag = 0, size = name.size();
	for (int i = 0; i < size; i++)
	{
		if (name[i] == str1)
		{
			a = i;
			flag = 1;
			break;
		}
	}

	if (flag == 0)
	{
		name.push_back(str1);
		a = name.size() - 1;
	}

	flag = 0;
	for (int i = 0; i < size; i++)
	{
		if (name[i] == str2)
		{
			b = i;
			flag = 1;
			break;
		}
	}

	if (flag == 0)
	{
		name.push_back(str2);
		b = name.size() - 1;
	}

	return make_pair(a, b);
}

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

문제

문제

출처

ICPC

시간초과 질문합니다

john6014 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말