[백준 1753번 C/C++] 최단경로

 

[백준 1753번 C/C++] 최단경로

 

https://www.acmicpc.net/problem/1753

1753번: 최단경로

---

 

해결전략

 

Dijkstra 다익스트라

 

---

 

처음 시도한 코드 - 시간초과

 

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

int v, e; // v: 정점의 개수, e: 간선의 개수
int k; // k: 시작 정점
vector<vector<int>> graph;

struct Edge {
	int vertex;
	int cost;
	Edge(int a, int b) {
		vertex = a;
		cost = b;
	}
	
	bool operator<(const Edge& e) const {
		return cost > e.cost;
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> v >> e;
	cin >> k;
	graph.resize(e, vector<int>(3));
	int x, y, z;
	for (int i = 0; i < e; i++){
		cin >> x >> y >> z;
		graph[i][0] = x;
		graph[i][1] = y;
		graph[i][2] = z;
	}

	vector<int> dist(v + 1, 2147000000);

	priority_queue<Edge> pQ;
	pQ.push({ k, 0 });
	dist[k] = 0;
	
	while (!pQ.empty())
	{
		int curV = pQ.top().vertex;
		int curC = pQ.top().cost;
		pQ.pop();

		if (dist[curV] < curC) continue;

		for (int i = 0; i < graph.size(); i++)
		{
			if (graph[i][0] == curV)
			{
				int nextV = graph[i][1];
				int nextC = curC + graph[i][2];

				if (dist[nextV] > nextC) {
					dist[nextV] = nextC;
					pQ.push({ nextV, nextC });
				}
			}
		}
	}

	for (int i = 1; i <= v; i++)
	{
		if (dist[i] == 2147000000) cout << "INF" << "\n";
		else cout << dist[i] << "\n";
	}

	return 0;
}

 

---

 

정답 코드

 

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

int v, e; // v: 정점의 개수, e: 간선의 개수
int k; // k: 시작 정점
vector<vector<pair<int, int>>> graph;

struct Edge {
	int vertex;
	int cost;
	Edge(int a, int b) {
		vertex = a;
		cost = b;
	}
	// 우선순위 큐에서 비용이 낮은 간선부터 뽑기 위해 연산자를 오버로딩
	bool operator<(const Edge& e) const {
		return cost > e.cost;
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> v >> e;
	cin >> k; 
	graph.resize(v + 1);
	int x, y, z;
	for (int i = 0; i < e; i++){
		cin >> x >> y >> z;
		graph[x].push_back({ y, z });
	}

	vector<int> dist(v + 1, 2147000000); // 각 정점까지의 최단 거리를 저장하는 벡터를 최대값으로 초기화

	priority_queue<Edge> pQ;
	pQ.push({ k, 0 }); // 시작 정점
	dist[k] = 0; 
	
	while (!pQ.empty())
	{
		int curV = pQ.top().vertex;
		int curC = pQ.top().cost;
		pQ.pop();

		if (dist[curV] < curC) continue; // 이미 처리된 정점인 경우 건너뛰고 다음 정점을 처리

		for (int i = 0; i < graph[curV].size(); i++) // 현재 정점과 연결된 간선을 모두 확인하면서 최단 거리를 갱신
		{
			int nextV = graph[curV][i].first;  // 다음 정점
			int nextC = curC + graph[curV][i].second; // 현재 정점까지의 경로 비용 + 다음 정점으로의 간선 비용
			
            // 현재까지의 최단 거리보다 더 짧은 경로를 발견한 경우 최단 거리를 갱신하고 큐에 새로운 간선을 추가
			if (dist[nextV] > nextC) {
				dist[nextV] = nextC;
				pQ.push({ nextV, nextC });
			}
		}
	}

	for (int i = 1; i <= v; i++) // 각 정점까지의 최단 거리를 출력
	{
		if (dist[i] == 2147000000) cout << "INF" << "\n";
		else cout << dist[i] << "\n";
	}

	return 0;
}

 

 

 

처음 시도한 코드와 차이점

    // 처음 시도한 코드
    vector<vector<int>> graph;
    graph.resize(e, vector<int>(3));
    int x, y, z;
    for (int i = 0; i < e; i++){
        cin >> x >> y >> z;
        graph[i][0] = x;
        graph[i][1] = y;
        graph[i][2] = z;
    }
    //...
    for (int i = 0; i < graph.size(); i++)
	{
    }
    //...

	// 정답 코드
	vector<vector<pair<int, int>>> graph;
    graph.resize(v + 1);
	int x, y, z;
	for (int i = 0; i < e; i++){
		cin >> x >> y >> z;
		graph[x].push_back({ y, z });
	}
    //...
    for (int i = 0; i < graph[curV].size(); i++) // 현재 정점과 연결된 간선을 모두 확인하면서 최단 거리를 갱신
    {
    }
    //...

---