백준 1753번 최단경로 C++

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

 

정점의 개수가 20000개여서 인접 행렬로 하면 20000*20000 = 400000000 (4억) 이라서 시간초과가 날 것 같아서 인접 리스트 방식으로 그래프를 만들고 다익스트라로 풀었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int v, e;

vector<vector<pair<int, int>>> vertexs;

struct VertexCost {
	bool operator<(const VertexCost& other) const {
		return cost < other.cost;
	}
	bool operator>(const VertexCost& other) const {
		return cost > other.cost;
	}
	int vertex;
	int cost;
};

void Dijikstra(int start) {
	vector<int> best(v + 1, INT_MAX);
	priority_queue<VertexCost, vector<VertexCost>, greater<VertexCost>> pq;
	pq.push({ start,0 });
	best[start] = 0;

	while (!pq.empty()) {
		auto curr = pq.top();
		pq.pop();

		if (curr.cost > best[curr.vertex])
			continue;

		for (auto a : vertexs[curr.vertex]) {
			int nextCost = curr.cost + a.second;
			if (nextCost >= best[a.first])
				continue;
			best[a.first] = nextCost;
			pq.push({ a.first,nextCost });
		}
	}
	for (int i = 1; i <= v; i++) {
		if (best[i] == INT_MAX)
			cout << "INF";
		else
			cout << best[i];
		cout << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> v >> e;
	int start;
	cin >> start;
	vertexs = vector<vector<pair<int, int>>>(v + 1, vector<pair<int, int>>());
	for (int i = 0; i < e; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		vertexs[a].push_back({ b,c });
	}
	Dijikstra(start);
};