글 읽기 - 시간초과 질문 (구조체 사용)

tnswh213 2년 전 0

사용한 언어는 C++을 사용했습니다. 왜 시간초과가 나는지 모르겠습니다.

#include <iostream>
#include <queue>
#include <memory.h>
using namespace std;

constexpr int INF = 9999999;
constexpr int MAX = 20001;
int V, E, K;

struct LINE
{
	int target;
	int weight;
};
struct cmp
{
	bool operator()(LINE& a, LINE& b)
	{
		return a.weight > b.weight;
	}
};

vector<LINE> graph[MAX];
int d[MAX];

void Find(int start);
int main()
{
	for (int i = 0; i < MAX; ++i)
		d[i] = INF;
	int u = 0, v = 0, w = 0;
	cin >> V >> E >> K;

	for (int i = 0; i < E; ++i) {
		cin >> u >> v >> w;
		LINE tmp = { v,w };
		graph[u].emplace_back(tmp);
	}
	int value = 0;


	Find(K);
	for (int i = 1; i <= V; ++i) {
	
		if (INF == d[i])
			cout << "INF" << endl;
		else
			cout << d[i]<< endl;
	
	}

}
void Find(int start)
{
	d[start] = 0;
	priority_queue<LINE, vector<LINE>, cmp> pq;
	pq.push({ start, 0 });

	while (!pq.empty())
	{
		int cur = pq.top().target;
		int dis = pq.top().weight;
		pq.pop();
		if (d[cur] < dis) continue;

		for (int i = 0; i < graph[cur].size(); ++i)
		{
			int next = graph[cur][i].target;
			int nextdis= dis+graph[cur][i].weight;
			if (d[next] > nextdis) {
				d[next] = nextdis;
				pq.push({ next,nextdis });
			}
		}
	}

}

aig0016 2년 전 1

66줄 부터 더 좋은 경로를 찾았을 때 시작점에서 각 노드까지의 거리가 저장된 배열 d를 갱신하지 않아서, 처음에 기록된 경로보다 짧은 경로를 계속 우선순위 큐에 넣다보니 시간초과가 난 것 같습니다.

tnswh213 2년 전 1

근데 구조체를 안쓰고
vector<pair<int,int>>를 사용하면 통과를 합니다. ㅜㅜ
그리고 short부분을 int로 바꾸었는데도 실패합니다.

aig0016 2년 전 1

제가 코드를 제대로 안 읽고 답글을 잘못 달았네요... 못 본 체 해주십쇼. 죄송합니다.

코드를 이렇게 바꾸셔야 됩니다.

그리고 20000*10라서 short 범위 넘기는 건 체크하신 것 같네요

	for (int i = 1; i <= V; ++i) {
	
		if (MAX == d[i]) // INF == d[i]
			cout << "INF" << endl;
		else
			cout << d[i]<< endl;
	
	}

tnswh213 2년 전 0

앗 제가 그부분 수정이 안되어있었네요 해당내용 수정했는데도 시간초과가 나옵니다.

aig0016 2년 전 0

출력 부분을 이렇게 바꿔보실래요...?

endl은 버퍼를 비우는 과정을 거치기 때문에 \n로 한 줄을 출력하는 것보다 느립니다.

더군다나 최대 2만줄 까지 출력하기 때문에 이걸로도 느려질 수 있다고 생각해요...

이게 아니면 다른 원인이 있다는 건데 이것 외에는 잘 안 보이네요

	for (int i = 1; i <= V; ++i) {
	
		if (MAX == d[i]) // INF == d[i]
			cout << "INF" << endl; // cout << "INF" << '\n';
		else
			cout << d[i]<< endl; // cout << d[i]<< '\n';
	
	}

tnswh213 2년 전 0

넵 감사합니다. 한번바꿔서 해볼께요!

tnswh213 2년 전 0

오 정말 endl말고 '\n'바꾸니깐 성공했어요 이것때매 안될줄을 몰랐어요 감사합니다.

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

문제

문제

출처

ICPC

시간초과 질문 (구조체 사용)

tnswh213 2년 전 0

aig0016 2년 전 1

tnswh213 2년 전 1

aig0016 2년 전 1

tnswh213 2년 전 0

aig0016 2년 전 0

tnswh213 2년 전 0

tnswh213 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말