글 읽기 - 우서순위큐.. endl 최적화.. 모르겠습니다.

arkingco 3년 전 0

질문 게시판에 있는 내용들은 대부분 적용한 것 같은데 시간초과가 계속 나옵니다 혹시 수정해야할 부분이 있을까요??

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

const int INF = 987654321;
int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int V, E, start;
	cin >> V >> E >> start;

	vector<pair<int, int> > adj[V+1];
	vector<int> dist(V+1, INF);
	priority_queue<pair<int, int> > pq;

	for(int i=0; i<E; ++i) {
		int from, to, val;
		cin >> from >> to >> val;
		
		adj[from].push_back(make_pair(val,to));
	}
	
	dist[start] = 0;
	pq.push({dist[start], start});
	while(!pq.empty()) {
		int here = pq.top().second;
		pq.pop(); 
		
		for(int i=0; i<adj[here].size(); ++i){
			int there = adj[here][i].second;
			int thereDistVal = adj[here][i].first;
			if(dist[there] > dist[here] + thereDistVal ) {
				dist[there] = dist[here] + thereDistVal;
				pq.push(make_pair(-thereDistVal, there));
			}
		}
	}
	
	for(int i=1; i<=V; ++i) {
		if(dist[i] == INF )
			cout << "INF" << '\n';
		else{
			cout << dist[i] << '\n';
		}
	}
}

shg9411 3년 전 1

다익스트라가 잘못되었습니다.

우선순위 큐에 집어넣는 거리 값을 사용하지 않고 계십니다.

Green55 3년 전 1

다익스트라 자체가 틀렸습니다. 같은 정점을 여러번 방문합니다.

arkingco 3년 전 0

다시 만들어 보겠습니다 !!!

arkingco 3년 전 0

해결 완료했습니다 !!!

혹시나 하는 분들 위해서 코드 추가 하겠습니당

	   // 수정 전 코드
        for(int i=0; i<adj[here].size(); ++i){
			int there = adj[here][i].second;
			int thereDistVal = adj[here][i].first;
			if(dist[there] > dist[here] + thereDistVal ) {
				dist[there] = dist[here] + thereDistVal;
				pq.push(make_pair(-thereDistVal, there));
			}
		}

       // 수정 후 코드 
       for(int i=0; i<adj[here].size(); ++i){
			int there = adj[here][i].second;
			int thereDistVal = adj[here][i].first;
           // 이부분 추가
			int nextDistVal = dist[here] + thereDistVal;
			if(dist[there] > dist[here] + thereDistVal ) {
                // 이부분 수정
				dist[there] = nextDistVal;
				pq.push(make_pair(-nextDistVal, there));
			}
		}

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

문제

문제

출처

ICPC

우서순위큐.. endl 최적화.. 모르겠습니다.

arkingco 3년 전 0

shg9411 3년 전 1

Green55 3년 전 1

arkingco 3년 전 0

arkingco 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말