백준 11404번 플로이드 C++

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

 

플로이드-와샬 알고리즘을 이용해서 쉽게 풀 수 있는 문제이다.

그리고 궁금해서 다익스트라로 모든 정점을 돌면서도 답을 구해봤는데 시간은 비슷하게 나왔다.

 

#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;

vector<vector<int>> graph;

const int INF = 987654321;

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

	int n, m;
	cin >> n >> m;

	vector<vector<int>> dist(n + 1, vector<int>(n + 1, INF));

	for (int i = 1; i <= n; i++) {
		dist[i][i] = 0;
	}

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		dist[a][b] = min(dist[a][b], c);
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (dist[i][k] + dist[k][j] >= dist[i][j])
					continue;
				dist[i][j] = dist[i][k] + dist[k][j];
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dist[i][j] == INF)
				cout << 0;
			else
				cout << dist[i][j];
			cout << " ";
		}
		cout << "\n";
	}
};

#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;

const int INF = 987654321;

int n, m;

vector<vector<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(n + 1, INF);
	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 (int i = 1; i <= n; i++) {
			if (vertexs[curr.vertex][i] == -1)
				continue;
			int nextCost = curr.cost + vertexs[curr.vertex][i];
			if (nextCost >= best[i])
				continue;
			best[i] = nextCost;
			pq.push({ i,nextCost });
		}
	}
	for (int i = 1; i <= n; i++) {
		if (best[i] == INF)
			cout << 0;
		else
			cout << best[i];
		cout << " ";
	}
	cout << "\n";
}

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

	cin >> n >> m;
	vertexs = vector<vector<int>>(n + 1, vector<int>(n + 1, INF));
	
	for (int i = 1; i <= n; i++) {
		vertexs[i][i] = 0;
	}

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		vertexs[a][b] = min(vertexs[a][b], c);
	}

	for (int i = 1; i <= n; i++) {
		Dijikstra(i);
	}
};