[백준/C++] 1238번: 파티

방법

코드

#include<bits/stdc++.h>
#define MAXN 1001
#define INF 987654321
using namespace std;

struct info {
	int n, w;
	info() {};
	info(int n, int w) :n(n), w(w) {};

	bool operator<(const info i) const {	// 오름차순
		return w > i.w;
	}
};

int n, m, x;
vector<info> g[MAXN];
vector<info> gt[MAXN];
bool check[MAXN];
int dp[MAXN];
int ans[MAXN];

void Dijkstra(int x, vector<info> graph[MAXN]) {
	for (int i = 0; i <= n; i++) {	// 초기화
		dp[i] = INF;
		check[i] = false;
	}
	priority_queue<info> pq;
	pq.push(info(x, 0));	// 시작점 넣기
	dp[x] = 0;
	while (!pq.empty()) {
		info cur = pq.top();
		pq.pop();
		if (check[cur.n]) continue;
		check[cur.n] = true;
		for (int z = 0; z < graph[cur.n].size(); z++) {
			int nxt_n = graph[cur.n][z].n;
			int nxt_w = graph[cur.n][z].w;
			if (nxt_w + dp[cur.n] < dp[nxt_n]) {
				dp[nxt_n] = nxt_w + dp[cur.n];
				pq.push(info(nxt_n, dp[nxt_n]));
			}
		}
	}
	for (int i = 0; i <= n; i++) {
		ans[i] += dp[i];
	}
}

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

	cin >> n >> m >> x;
	for (int i = 0, u, v, t; i < m; i++) {
		cin >> u >> v >> t;
		g[u].push_back(info(v, t));
		gt[v].push_back(info(u, t));	// 방향 바꾸기
	}

	Dijkstra(x, g);
	Dijkstra(x, gt);

	int m = 0;
	for (int i = 1; i <= n; i++) {
		m = max(m, ans[i]);
	}
	cout << m;

	return 0;
}