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

kth 5년 전 0

다익스트라를 우선순위큐를 사용해서 구현했는데... 어느 부분에서 시간초과가 나는지 또는 틀렸는지 모르겠습니다. 알려주실 수 있나요?

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

const int INF = 10000000;
int V, E, K, u, v, w;
vector<pair<int, int>>adj[20001];
int dist[20001];

void dijstra(int start);

int main() {
	ios::sync_with_stdio(false);
	scanf("%d %d %d", &V, &E, &K);
	for (int i = 0; i < E; i++) {
		scanf("%d %d %d", &u, &v, &w);
		adj[u].push_back(make_pair(v, w));
	}
	dijstra(K);
	for (int i = 1; i <= V; i++) {
		if (dist[i] == INF)
			printf("INF\n");
		else
			printf("%d\n", dist[i]);
	}
}

void dijstra(int start) {
	for (int i = 1; i <= V; i++)
		dist[i] = INF;
	dist[start] = 0;
	priority_queue<pair<int, int>> pq;//힙 구조
	pq.push(make_pair(start, 0));
	while (!pq.empty()) {
		int here = pq.top().first;
		//minHeap구조
		int cost = -pq.top().second;
		pq.pop();
		if (dist[here] < cost)
			continue;
		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first;
			int nextdist = cost + adj[here][i].second;
			if (dist[there] > nextdist) {
				dist[there] = nextdist;
				//minHeap을 만들기 위해 음수값 우선순위큐에 추가
				pq.push(make_pair(there, -nextdist));
			}
		}
	}
}

djm03178 5년 전 1

https://www.acmicpc.net/board/...

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

문제

문제

출처

ICPC

시간초과나서 질문드립니다.

kth 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말