백준 1719 - 택배(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1719

1719번: 택배

다익스트라를 이용해 푸는 문제입니다.

거리를 출력하는 것이 아닌, 최단거리를 가기 위해서 처음으로 가는 정점을 출력하면 됩니다.

즉, 기본적인 다익스트라를 사용하면서, 거리가 바뀔 때마다 가는 정점을 같이 바꿔줘야한다는 의미입니다.

먼저 1~N까지 모두 출력해야 하기에 반복문을 통해 i번 정점을 기준으로 탐색을 시작할 수 있도록 해줍니다.

정점에서 탐색을 시작했다면 이제 갈 수 있는 곳들을 최단 경로를 통해 확인해줍니다. -> 이때 다익스트라 알고리즘이 사용됩니다.

경로의 값을 저장하는 Distance배열이 이때 달라지는데, 기존처럼 경로의 길이만 저장하는 것이 아닌, i번 정점에서 처음으로 이동한 정점도 같이 저장해줍니다.

따라서 길이가 바뀐다는 뜻은, 이동하는 정점이 달라졌다는 의미이니, 해당 경우가 저장하고 있는 처음 정점 값으로 바꿔줍니다.

혹은, 처음 이동하는 경우라면 해당 경우에서 처음 이동하는 정점을 저장해주면 됩니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#define INF 2100000000
#define F first
#define S second

using namespace std;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
int N, M;
pair<int, int> Distance[201];
bool check[201];
vector<pair<int, int>> connect[201];

void reset_distance(){
	for(int i = 1; i <= N; i++) Distance[i] = {INF, -1}; //최단거리 뿐만 아닌 어디를 처음으로 방문하는지도 저장한다.
	for(int i = 1; i <= N; i++) check[i] = false;
}

void dijstra(int start){
	Distance[start] = {0, -1};
	q.push({Distance[start].F, start}); //거리와 시작지점을 저장
	while(!q.empty()){
		int x = q.top().S;
		int cost = q.top().F;
		check[x] = true;
		q.pop();
		for(int i = 0; i < connect[x].size(); i++){
			int xx = connect[x][i].F;
			int Cost = connect[x][i].S;
			if(!check[xx] && Distance[xx].F > Distance[x].F + Cost){ //이번에 가는 방법이 저번 방법보다 거리가 작다면
				Distance[xx].F = Distance[x].F + Cost;
				if(x == start) Distance[xx].S = xx; // 아직 출발하지 않은 정점이라면 처음 가는 곳을 저장해준다.
				else Distance[xx].S = Distance[x].S; // 이전에 값이 저장되어 있다면 새로운 값을 넣어준다.
				q.push({Distance[xx].F, xx});
			}
		}
	}
}

void solve(){
	for(int i = 1; i <= N; i++){ // 모든 경우를 확인해줘야 하기에 반복문을 통해 확인할 수 있도록 한다.
		reset_distance();
		dijstra(i);
		for(int j = 1; j <= N; j++){
			if(i == j) cout << "-" << " ";
			else cout << Distance[j].S << " ";
		}
		cout << "\n";
	}
}


int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;	
	for(int i = 1; i <= M; i++){
		int x, y, cost;
		cin >> x >> y >> cost;
		connect[x].push_back({y, cost});
		connect[y].push_back({x, cost});
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.