글 읽기 - 시간초과가 자꾸 나네요...방법은 맞는 것 같은데요!

jack2020 5년 전 0

4퍼에서 시간초과로 끊기네요 ㄷㄷ

예제는 정답이고 딱히 시간 끌만한 부분도 있지는 않는 것 같은데...ㅠ

한 번만 도와주시면 감사하겠습니다! ㅠ

#include <cstdio>
#include <queue>
#include <vector>
#define INF 10000000
using namespace std;


priority_queue<pair <int, int> > pq;
vector<pair<pair<int, int>,int> > graph;

int V, E, K = 0;
int dist[20001];

int main() {
	scanf("%d %d", &V, &E);
	scanf("%d", &K);
	for (int i = 1; i <= E; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		graph.push_back({{a, b}, c});
	}
	for (int i = 1; i <= V; i++) {
		if (i == K) {
			dist[i] = 0;
		} else {
			dist[i] = INF;
		}
	}
	pq.push({0, K});
	while (pq.size() != 0) {
		pair<int, int> x = pq.top();
		for (int i = 0; i <= (int) graph.size() - 1; i++) {
		    if (graph[i].first.first == x.second) {
		    	if (dist[graph[i].first.second] > x.first + graph[i].second) {
		    		dist[graph[i].first.second] = x.first + graph[i].second;
		    		pq.push({dist[graph[i].first.second] , graph[i].first.second});
		    	} 
		    }
		}
		pq.pop();
	}
	for (int i = 1; i <= V; i++) {
		if (dist[i] == INF) {
			printf("INF\n");
		} else {
			printf("%d\n", dist[i]);
		}
	}
	return 0;
}

djm03178 5년 전 1

2만 개의 정점에 대해 30만개의 간선을 모두 체크하니까 약 60억으로 시간 초과가 맞습니다. 정점마다 인접 리스트를 만들면 전체 루프에서 30만개의 간선만 확인하면 됩니다.

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

문제

문제

출처

ICPC

시간초과가 자꾸 나네요...방법은 맞는 것 같은데요!

jack2020 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말