글 읽기 - 1753 최단경로 시간초과 질문

qocn9029 3년 전 0

1753 다익스트라 최단경로 질문입니다. pa 구조체를 만들어서 각각 노드번호와 거리를 저장하였습니다. 그런데 dijkstra 함수안 for문에서 최단거리를 갱신및 연결되있는 그래프 노드를 탐색하는데 저 정도 반복은 해야될거같은데 시간초과가 뜹니다. 출발노드 도착노드 거리를 저장해놓은 2차원 벡터를 탐색하는데 시간이 너무 오래걸린걸까요? 수정해야하는데 감을 못잡겠습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

#define MAX 200000000

struct pa {
	int x;
	int y;
};

struct cmp {
	bool operator()(pa a, pa b) {
		return a.y < b.y;//거리가 작은게 먼저 나오도록 해주는 비교클래스
	}
};

vector<pa> graph[20001];
int D[20001];

void dijkstra(int first) {
	priority_queue<pa, vector<pa>, cmp> q;//min heap
	pa tmp;
	tmp.x = first;
	tmp.y = 0;

	q.push(tmp);

	while (!q.empty()) {
		pa next = q.top();
		q.pop();

		for (int i = 0; i < graph[next.x].size(); i++) {
			int k = graph[next.x][i].x;//2

			if (D[k] <= D[next.x] + graph[next.x][i].y){
				continue;
			}

			D[k] = D[next.x] + graph[next.x][i].y;
			pa dt;
			dt.x = graph[next.x][i].x;
			dt.y = graph[next.x][i].y;
			q.push(dt);
		}
	}
	return;
}

int main() {
	int n, m;
	int start;
	scanf("%d %d", &n, &m);
	scanf("%d", &start);

	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);

		pa data;
		data.x = b;
		data.y = c;
		graph[a].push_back(data);
	}

	for (int i = 1; i <= n; i++) {
		D[i] = MAX;
	}

	D[start] = 0;
	dijkstra(start);

	for (int i = 1; i <= n; i++) {
		if (D[i] == MAX) {
			printf("INF\n");
		}

		else printf("%d\n", D[i]);
	}
	return 0;
}

kgstiger 3년 전 1

앞으로 갈 곳의 경로가 이미 더 작은 값을 가지고 있을때에도 계속해서 탐색해서 그런것 같습니다.

for문을 돌기전에 dist[now]<cost 라면 이미 더 작은 경로값을 알고 있는 것이기 때문에 continue를 해야

시간을 아낄 수 있습니다.

qocn9029 3년 전 0

감사합니다!

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

문제

문제

출처

ICPC

1753 최단경로 시간초과 질문

qocn9029 3년 전 0

kgstiger 3년 전 1

qocn9029 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말