글 읽기 - 시간초과가 어디서 나는지 궁금합니다.

yhj010597 4년 전 0

시간초과가 어디서 나는지 궁금합니다.

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

const int MAX = 20000 + 1;

int V,E;
int startPoint;
vector<pair<int,int>> dArr[MAX+1];
int d[MAX+1];

void f(int start){
	d[start] = 0;
	priority_queue<pair<int,int>> pq;
	pq.push(make_pair(start,0));
	
	while(!pq.empty()){
		int current = pq.top().first;
		int distance = -pq.top().second;
		pq.pop();
		
		if(d[current] < distance) continue;
		
		for(int i=0;i< dArr[current].size();i++){
			int next = dArr[current][i].first;
			int nextDistance = distance + dArr[current][i].second;
			
			if(nextDistance < d[next]){
				d[next] = nextDistance;
				pq.push(make_pair(next,-nextDistance));
			}
		}
	}
}

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	
	cin >> V >> E;
	cin >> startPoint;
	
	V++;	
	
	int W;
	int a,b;
	
	for(int i=1;i<=V;i++){
		d[i] = 987654321;
	}
	
	for(int i=0;i<E;i++){
		cin >> a >> b >> W;
		dArr[a].push_back(make_pair(b,W));
	}
	
	f(startPoint);
	
	for(int i=1;i<V;i++){
		if(d[i] == 987654321) cout << "INF\n";
		else cout << d[i] << "\n";
	}
}

djm03178 4년 전 0

질문을 올릴 때 위에 읽으라고 나오는 공지사항에 굵은 글씨로 적힌 대로 질문 검색을 통해 다른 질문들을 먼저 찾아보시지 않았기 떄문에 시간 초과가 발생합니다.

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

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

문제

문제

출처

ICPC

시간초과가 어디서 나는지 궁금합니다.

yhj010597 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말