백준 11779 - 최소비용 구하기 2(C++)

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

11779번: 최소비용 구하기 2

다익스트라 알고리즘을 사용하는 문제입니다.

https://junseok.tistory.com/188

백준 1916 - 최소비용 구하기(C++)

해당 문제에서 길을 저장해주면 되는 문제였습니다.

백터를 만들어서 X번째 정점에서의 거쳐온 길을 저장해줬습니다.

 

 

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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#define INF 210000000000

using namespace std;

priority_queue<pair<long long int, int>, vector<pair<long long int, int>>, greater<pair<long long int, int>>> q;
int N, M;
int start, finish;
long long int Distance[1001];
bool check[1001];
vector<pair<int, int>> connect[1001];
vector<int> way[1001];

void reset_Distance() {
	for (int i = 1; i <= N; i++) {
		Distance[i] = INF;
	}
}

void solve() {
	reset_Distance();
	memset(check, false, sizeof(check));
	Distance[start] = 0;
	way[start].push_back(start);
	q.push(make_pair(Distance[start], start));
	while (!q.empty()) {
		int x = q.top().second;
		int cost = q.top().first;
		q.pop();
		check[x] = true;
		if (x == finish) {
			break;
		}
		for (int i = 0; i < connect[x].size(); i++) {
			int xx = connect[x][i].first;
			int Cost = connect[x][i].second;
			if (!check[xx] && Distance[xx] > Distance[x] + Cost) {
				Distance[xx] = Distance[x] + Cost;
				way[xx] = way[x];
				way[xx].push_back(xx);
				q.push(make_pair(Distance[xx], xx));
			}
		}
	}
	cout << Distance[finish] << "\n" << way[finish].size() << "\n";
	for (int i = 0; i < way[finish].size(); i++) {
		cout << way[finish][i] << " ";
	}
}

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(make_pair(y, cost));
	}
	cin >> start >> finish;
	solve();
	return 0;
}

 

 

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