백준 1238 파티 풀이

문제

요약

• n명의 남학생이 x에서 파티를 벌이고 집으로 되돌아가려함
• 도로는 단방향임
• 게을러서 최단 시간이 오고 가기를 원함
• 오고 가는데 가장 많은 시간을 소비하는 학생은?

접근

• 방향성을 갖고 있는 도로이므로 파티장으로 갈땐 플로이드와샬(다대일이므로) 파티장에서 집으로 올땐(다익스트라 일대다이므로)으로 최단 시간을 구해주면 된다.

풀이

1. 플로이드로 모든 마을에서 x까지 가는최단거리를 구한다.
2. 다익스트라로 x에서 모든 마을까지 가는 최단거리를 구한다.

소스

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int INF = (int)1e9;
struct vertex {
	int index, weight;

	bool operator < (const vertex& v) const {
		return this->weight > v.weight;
	}
};

int n, m, x;
vector<vertex> adj[1001];
int graph[1001][1001];
int dist[1001];
bool visited[1001];

void dijkstra() {
	fill(&dist[0], &dist[n + 1], INF);
	dist[x] = 0;

	priority_queue<vertex> pq;
	pq.push({ x, 0 });
	while (!pq.empty()) {
		int cur = pq.top().index;
		pq.pop();
		visited[cur] = true;
		for (vertex& next : adj[cur]) {
			if (!visited[next.index] &&
				 dist[next.index] > dist[cur] + next.weight) {
				dist[next.index] = dist[cur] + next.weight;
				pq.push({ next.index, dist[next.index] });
			}
		}
	}

}

void floydwarshall() {
	for (int by = 1; by <= n; ++by) {
		for (int from = 1; from <= n; ++from) {
			for (int to = 1; to <= n; ++to) {
				if (from == to)continue;
				if (graph[from][by] + graph[by][to] < graph[from][to]) {
					graph[from][to] = graph[from][by] + graph[by][to];
				}
			}
		}
	}
	
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> x;
	fill(&graph[0][0], &graph[1000][1001], INF);
	for (int i = 0; i < 1001; ++i)
		graph[i][i] = 0;
	int a, b, c;
	while (m--) {
		cin >> a >> b >> c;
		adj[a].push_back({ b, c });
		graph[a][b] = c;
	}
	floydwarshall();
	dijkstra();

	int res = 0;
	for (int i = 1; i <= n; ++i) {
		if (res < graph[i][x] + dist[i]) {
			res = graph[i][x] + dist[i];
		}
	}
	cout << res << endl;
	return 0;
}

다 풀고 보니 내 소스가 다른 사람들 소스보다 눈에 띄게 느렸다.. 플로이드가 O(n^3)이라 엄청나게 느린거였는데..

생각해보니 다대일인 경우도 길을 거꾸로 연결해주면 일대다로 바뀌어 다익으로 풀 수 있다는걸 알지 못했었다… ㄷㄷ 똑똑하구만

무려 0ms대 소스로 탈바꿈한다.. ㄷㄷ

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int INF = (int)1e9;
struct vertex {
	int index, weight;

	bool operator < (const vertex& v) const {
		return this->weight > v.weight;
	}
};

int n, m, x;
vector<vertex> adj[1001], rev_adj[1001];


vector<int> dijkstra(vector<vertex> v[1001]) {
	vector<int> dist(n + 1, INF);
	bool visited[1001] = {};
	dist[x] = 0;

	priority_queue<vertex> pq;
	pq.push({ x, 0 });
	while (!pq.empty()) {
		int cur = pq.top().index;
		pq.pop();
		visited[cur] = true;
		for (vertex& next : v[cur]) {
			if (!visited[next.index] &&
				dist[next.index] > dist[cur] + next.weight) {
				dist[next.index] = dist[cur] + next.weight;
				pq.push({ next.index, dist[next.index] });
			}
		}
	}
	return dist;
}


int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> x;
	int a, b, c;
	while (m--) {
		cin >> a >> b >> c;
		adj[a].push_back({ b, c });
		rev_adj[b].push_back({ a, c });
	}

	vector<int> go = dijkstra(rev_adj);
	vector<int> back = dijkstra(adj);

	int res = 0;
	for (int i = 1; i <= n; ++i) {
		if (res < go[i] + back[i]) {
			res = go[i] + back[i];
		}
	}
	cout << res << endl;
	return 0;
}