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

gpotatok 3년 전 0

다익스트라 알고리즘 사용했고 우선순위 큐에서 거리 짧은 순으로 뽑히는거도 확인했는데도 시간 초과가 발생합니다... 어느 부분에서 문제가 생기는건지 알려주시면 감사하겠습니다.

#include <iostream>
#include <queue>
#include <vector>
#define INF 2147483647

using namespace std;

int vertexNum, edgeNum;
int startVertex;

struct Edge {
	Edge(int e, int d): end(e), distance(d) {}
	int end, distance;
};

class Vertex {
public:
	int number;
	int minDistance;
	vector<Edge*> edgeTo;
	int edgeNum;
	bool visited;

	Vertex(int n) {
		this->number = n;
		this->minDistance = INF;
		this->edgeNum = 0;
		this->visited = false;
	}
	// ~Vertex() {
		
	// }
	
	void setMinDistance(int d) {
		this->minDistance = d;
	}
	
	void addEdge(Edge* e) {
		this->edgeTo.push_back(e);
		this->edgeNum++;
	}
	
};

Vertex* vertexArr[20001];

struct isShorter {
	bool operator() (Vertex* v1, Vertex* v2) {
		return (v1->minDistance) > (v2->minDistance);
	}
};

priority_queue<Vertex*, deque<Vertex*>, isShorter> toVisit;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	
	cin >> vertexNum >> edgeNum;
	for (int i = 1; i <= vertexNum; i++) {
		vertexArr[i] = new Vertex(i);
	}
	
	cin >> startVertex;
	vertexArr[startVertex]->setMinDistance(0);
	
	int start, end, dist;
	for (int i = 0; i < edgeNum; i++) {
		cin >> start >> end >> dist;
		vertexArr[start]->addEdge(new Edge(end, dist));
		
	}
	
	toVisit.push(vertexArr[startVertex]);
	Vertex* v;
	int tempEnd, tempDist;
	
	while (!toVisit.empty()) {	// 우선순위큐 다익스트라
		v = toVisit.top();
		toVisit.pop();
		v->visited = true;
		
		for (int i = 0; i < v->edgeNum; i++) {
			tempEnd = v->edgeTo[i]->end;
			tempDist = (v->minDistance + v->edgeTo[i]->distance);
			if (tempDist < vertexArr[tempEnd]->minDistance) {
				vertexArr[tempEnd]->setMinDistance(tempDist);
			}
			
			if (!(vertexArr[tempEnd]->visited)) {
				toVisit.push(vertexArr[tempEnd]);
			}
		}
	}
	
	for (int i = 1; i <= vertexNum; i++) {
		if (vertexArr[i]->minDistance == INF) {
			cout << "INF\n";
		}
		else cout << vertexArr[i]->minDistance << '\n';
	}
}

ikeelee7742 3년 전 1

저도 이런식으로 짜본적은 없어서 다익스트라에 문제가 있을 것 같아 살펴봤는데
이런식으로 다음 노드의 최솟값을 갱신시켜줄 때 그 위치를 큐에 넣어주니까 시간초과를 면하네요

그리고 현재 노드를 탐색하기 전에 이미 최솟값이 갱신되어있으면 그냥 continue해주면 더 빠릅니다

	while (!toVisit.empty()) {	// 우선순위큐 다익스트라
		v = toVisit.top();
		toVisit.pop();
		v->visited = true;

		//if (vertexArr[v->number]->minDistance < v->minDistance) continue;
		for (int i = 0; i < v->edgeNum; i++) {
			tempEnd = v->edgeTo[i]->end;
			tempDist = (v->minDistance + v->edgeTo[i]->distance);
			if (tempDist < vertexArr[tempEnd]->minDistance) {
				vertexArr[tempEnd]->setMinDistance(tempDist);
				toVisit.push(vertexArr[tempEnd]);
			}

			//if (!(vertexArr[tempEnd]->visited)) {
			//	toVisit.push(vertexArr[tempEnd]);
			//}
		}
	}

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

문제

문제

출처

ICPC

시간 초과 질문입니다..

gpotatok 3년 전 0

ikeelee7742 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말