[C++/다익스트라] 1753 : 최단경로

오답

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

#define MAX 20010
#define INF 987654321

using namespace std;

int V, E, start;
vector<pair<int, int>> a[MAX];
int d[MAX];

void dijkstra(){
	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<a[current].size() ; i++){   
			int next = a[current][i].first;          
			int nextDistance = distance + a[current][i].second;  
		
			if(nextDistance < d[next]){                
				d[next]=nextDistance;                
				pq.push(make_pair(next, -nextDistance));
			}  
		}	
	}
}

int main(void) {
	//cin,cout의 속도를 줄여주는 코드
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> V >> E >> start;

	for (int i = 1; i <= V; i++) {
		d[i] = INF;
	}

	for (int i = 0; i < E; i++) {
		int v1, v2, e;
		cin >> v1 >> v2 >> e;
		a[v1].push_back(make_pair(v2, e));
	}

	dijkstra();
	for (int i = 1; i <= V; i++) {
		if (d[i] == INF) cout << "INF" << "\n";
		else cout << d[i] << "\n";
	}
	return 0;
}

priority_queue<pair<int,int>>는 첫번째 인자를 기준으로 작은 값이 먼저 쌓인다. 첫번째 인자 값이 같을 경우 두번째 인자 값을 비교한다.

위 코드에서 우선순위 큐의 첫번째 인자는 노드이다.

이 경우엔 선형 탐색이나 다름 없다. BFS와 크게 다르지 않다.

 

아래 코드에선 우선순위 큐의 첫번째 인자를 가중치로 주어 최소 가중치에 해당하는 노드를 먼저 탐색하도록 했다.

(pq에선 첫번째 인자를 가중치로 주고 a변수 에선 첫번째 인자를 노드로 주어 헤맸다.)

 

 

정답

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

#define MAX 20010
#define INF 987654321

using namespace std;

int V, E, start;
vector<pair<int, int> > a[MAX];
int d[MAX];

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

int main(void) {
	//cin,cout의 속도를 줄여주는 코드
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> V >> E >> start;

	for (int i = 1; i <= V; i++) {
		d[i] = INF;
	}

	for (int i = 0; i < E; i++) {
		int v1, v2, e;
		cin >> v1 >> v2 >> e;
		a[v1].push_back(make_pair(v2, e));
	}

	dijkstra();
	for (int i = 1; i <= V; i++) {
		if (d[i] == INF) cout << "INF" << "\n";
		else cout << d[i] << "\n";
	}
	return 0;
}