이것이 코딩테스트다 - 9) 최단 경로 찾기

 

 

 

 

다이나믹프로그래밍에 이어서 눈물만 나오는...^^

 

꼭 다시풀자 😂

 

 

 

9.1) 미래 도시

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define INF 1e9


using namespace std;


int n, m, x, k;
int graph[101][101];


int main() {

	cin >> n >> m;

	for (int i = 0; i < 101; i++)
	{
		fill(graph[i], graph[i] + 101, INF);
	}
	for (int i = 1; i < n + 1; i++) {
		for (int j = 1; j < n + 1; j++) {
			if (i == j) graph[i][j] = 0;
		}
	}
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		graph[a][b] = 1;
		graph[b][a] = 1;
	}

	cin >> x >> k;

	for (int k = 1; k < n + 1; k++)
	{
		for (int a = 1; a < n + 1; a++)
		{
			for (int b = 1; b < n + 1; b++) {
				graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]);
			}
		}
	}

	int distance = graph[1][k] + graph[k][x];

	if (distance >= INF) cout << "-1";
	else cout << distance << endl;

	return 0;
}

 

 

 

9.2) 전보

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define INF 1e9


using namespace std;

int n, m, start;
vector <pair <int, int>> graph[30001];

int d[30001];

void dijkstra(int start) {

	priority_queue <pair<int, int>> pq;
	pq.push({ 0,start });
	d[start] = 0;
	while (!pq.empty()) {
		int dist = -pq.top().first;
		int now = pq.top().second;

		pq.pop();

		if (d[now] < dist)continue;
		for (int i = 0; i < graph[now].size(); i++)
		{
			int cost = dist + graph[now][i].second;
			if (cost < d[graph[now][i].first])
			{
				d[graph[now][i].first] = cost;
				pq.push(make_pair(-cost, graph[now][i].first));
			}
		}
	}
}

int main() {

	cin >> n >> m >> start;
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		graph[x].push_back({ y, z });
	}

	fill(d, d + 30001, INF);


	dijkstra(start);

	int count = 0;

	int maxDistance = 0;

	for (int i = 1; i <= n; i++)
	{
		if (d[i] != INF)
		{
			count += 1;
			maxDistance = max(maxDistance, d[i]);
		}
	}

	cout << count - 1 << ' ' << maxDistance << endl;



	return 0;
}