글 읽기 - 시간초과 질문드립니다.

adfsfsf 5년 전 0

아래와 같은 코드에서, 우선순위 큐를 굳이 그대로 둬야 할까요? 그냥 큐 배열을 만드는 게 더 나을까요?

#include <cstdio>
#include <queue>
#include <list>
#pragma warning(disable : 4996)
using namespace std;
struct map {
	long int price = -1;
	long int b = -1;
};
struct info {
	long int price = -1, startp;
	bool check = false;
	queue<map> b;
};
struct cmp {
	bool operator()(info a, info b) {
		if (a.check && b.check)
		{
			if (a.price == b.price)
				return a.startp > b.startp;
			if (a.price == -1 && b.price != -1)
				return true;
			if (a.price != -1 && b.price == -1)
				return false;
			return a.price > b.price;
		}
		if (a.check && !b.check)
			return true;
		if (!a.check&&b.check)
			return false;
		if (a.price == b.price)
			return a.startp > b.startp;
		if (a.price == -1 && b.price != -1)
			return true;
		if (a.price != -1 && b.price == -1)
			return false;
		return a.price > b.price;
	}
};
int main(void)
{
	long int v, e, start, i, j, a, len;
	priority_queue<info, vector<info>, cmp> maps;
	info *node;
	info node2;
	map *node1;
	map alpha;
	scanf("%ld %ld", &v, &e);
	scanf("%ld", &start);
	node = new info[v];
	for (i = 0; i < e; i++)
	{
		scanf("%ld", &a);
		node1 = new map;
		scanf("%ld %ld", &node1->b, &node1->price);
		node[a - 1].b.push(*node1);
	}
	node[start - 1].price = 0;
	while (true)
	{
		alpha = node[start - 1].b.front();
		node[start - 1].b.pop();
		node[alpha.b - 1].price = alpha.price;
		if (node[start - 1].b.size() == 0)
			break;
	}
	node[start - 1].check = true;
	for (i = 0; i < v; i++)
	{
		node[i].startp = i;
		maps.push(node[i]);
	}
	while (!maps.top().check)
	{
		node2 = maps.top();
		node[node2.startp].check = true;
		len = node2.b.size();
		for (i = 0; i < len; i++)
		{
			alpha = node2.b.front();
			node2.b.pop();
			if (node[alpha.b - 1].price == -1)
				node[alpha.b - 1].price = node2.price + alpha.price;
			else
				node[alpha.b - 1].price = node[alpha.b - 1].price < (node2.price + alpha.price) ? node[alpha.b - 1].price : (node2.price + alpha.price);
		}
		while (maps.size() != 0)
			maps.pop();
		for (i = 0; i < v; i++)
			maps.push(node[i]);
	}
	for (i = 0; i < v; i++)
	{
		if (node[i].price == -1)
			printf("INF\n");
		else
			printf("%ld\n", node[i].price);
	}
	return 0;
}

seico75 5년 전 1

코드는 복잡하고 질문은 짧군요.

이 코드와 질문의 핵심은 push 할때 복사해서 들어가서 node 를 조작한 것이 maps 에 반영이 안되는 것이 아닌가 합니다.

일단 질문하신 것에 대한 의견은...

. priority_queue 는 유지하되 node 인 index만 넣고

. cmp 함수에서 node[index_a], node[index_b] 를 비교하게 하고

. while loop 에서는 node 를 수정하면 되지 않을까요?

그리고 54번줄에서 new 하지 말고 그냥 변수 잡고 push 해도 되지 않을까요. leak 도 없고.. (저 할당은 다 leak 이 될 것 같습니다.)

adfsfsf 5년 전 0

VS는 leak이 없어서 신경 안 쓰고 있었는데... 코드가 길어지면 신경써야겠군요. 제가 다른 예제들을 더 살피고 와야겠군요. 감사합니다.

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

문제

문제

출처

ICPC

시간초과 질문드립니다.

adfsfsf 5년 전 0

seico75 5년 전 1

adfsfsf 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말