1916 최소비용 구하기

#include <iostream>
#include <vector>
#include <queue>
#define MAX_N 1001
#define INF ~0U >> 2
using namespace std;

int N, M, s, f;
vector<pair<int, int>> adj[MAX_N];
vector<int> dist;

void dijkstra(int src) {
	dist[src] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, src));
	while (!pq.empty()) {
		int cost = -pq.top().first;
		int here = pq.top().second;
		pq.pop();
		if (dist[here] < cost) continue;
		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first;
			int nextDist = adj[here][i].second + cost;
			if (dist[there] > nextDist) {
				dist[there] = nextDist;
				pq.push(make_pair(-nextDist, there));
			}
		}
	}
}


int main() {
	cin >> N >> M;
	dist = vector<int>(N + 1, INF);
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].emplace_back(make_pair(b, c));
	}
	cin >> s >> f;
	dijkstra(s);
	cout << dist[f];

}

그냥 다익스트라 알고리즘 원형 코드랑 똑같다
코드 익히는 용으로 한 번 풀어본 셈 치자.

1238 파티

#include <iostream>
#include <vector>
#include <queue>
#define MAX_N 1001
#define INF ~0U >> 2
using namespace std;

int N, M, X;
vector<pair<int, int>> adj[MAX_N];
vector<int> comeCost;

vector<int> dijkstra(int src) {
	vector<int> dist(N + 1, INF);
	priority_queue<pair<int, int>> pq;
	dist[src] = 0;
	pq.push(make_pair(0, src));

	while (!pq.empty()) {
		int cost = -pq.top().first;
		int here = pq.top().second;
		pq.pop();
		if (dist[here] < cost) continue;
		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first;
			int nextDist = adj[here][i].second + cost;
			if (dist[there] > nextDist) {
				dist[there] = nextDist;
				pq.push(make_pair(-nextDist, there));
			}
		}
	}
	return dist;
}

int main() {
	cin >> N >> M >> X;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].emplace_back(make_pair(b, c));
	}
	int max = 0;
	comeCost = dijkstra(X);
	for (int i = 1; i <= N; i++) {
		int now = i == X ? 0 : dijkstra(i)[X] + comeCost[i];
		max = now > max ? now : max;
	}
	cout << max;
}

이 문제에서 고려해야 할 점은 반드시 X에 방문해야 한다는 것이다.
i에서 X로 가는 길의 최소 경로 + X에서 i로 돌아오는 길의 최소 경로 를 더하면 구할 수 있다.
X에서 i로 돌아오는 길의 최소 경로는 매번 계산하지 않고, comeCost 배열에 저장해두었다.