글 읽기 - [C++] 78프로에 시간초과가 발생합니다

tpgns97 2년 전 0

78프로에 시간초과로 종료되어집니다.

아직 미숙하지만 혹시, 이유가 무엇인지 고수님들께서 제가 놓친 부분들을 한번 지적해주시면 감사하겠습니다 :)

#include<iostream>
#include<utility>
#include<queue>
#include<vector>


#define INF 21000000 //INF 값


using namespace std;


struct comp {
	bool operator()(pair<int, int>& X, pair<int, int>& Y)
	{
		return X.second < Y.second;
	}
}; //우선순위 큐 비교기준 설정

priority_queue<pair<int, int>, vector<pair<int, int>>, comp> arr; //우선순위 큐 
//->  첫번째 인자가 Vertex, 두번째 인자의 경우 Weight

vector<pair<int, int>> Arr[20001]; //인접리스트
 
int dis[20001] = { 0, };

void dijkstra(int S_V, int V)
{
	for (int i = 1; i <= V; i++){ dis[i] = INF;} dis[S_V] = 0;
	pair<int, int> temp;
	arr.push(make_pair(S_V, dis[S_V]));
	while (!arr.empty())
	{
		temp = arr.top();
		arr.pop();
		for (int i = 0; i < Arr[temp.first].size(); i++)
		{
			if (dis[Arr[temp.first][i].first] > (dis[temp.first] + Arr[temp.first][i].second))
			{
				dis[Arr[temp.first][i].first] = dis[temp.first] + Arr[temp.first][i].second;
				arr.push(Arr[temp.first][i]);
			}

		}
	}
}

int main(void)
{

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int V, E, S_V; cin >> V >> E >> S_V;
	
	for (int i = 0; i < E; i++) 
	{ 
		int from, to, w;  cin >> from >> to >> w; 
		Arr[from].push_back(make_pair(to, w)); 
	}
	dijkstra(S_V, V);
	
	for (int i = 1; i <= V; i++) {
		if (dis[i] ==INF) { cout << "INF" << "\n"; }
		else { cout << dis[i] << "\n"; }
	}

}

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

문제

문제

출처

ICPC

[C++] 78프로에 시간초과가 발생합니다

tpgns97 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말