[PS] 임계경로 / C++ (백준 1948번)

임계경로 (백준 1948번)

 

DAG(방향 비순환 그래프)를 항상 만족하는 상황에서 최장거리를 구하는 문제.

 

풀이 과정

• 처음엔 다익스트라 스타일로 최장 거리를 구하는 스타일로 풀어서 AC를 받았지만, 분명 $O(MlogN)$인데 시간이 너무 오래 걸렸다.
  • 다익스트라 느낌으로 prique를 써서 역방향 탐색하며 역추적을 위해 _next 벡터에 다음 node를 저장하면서 진행했는데, 생각해보니 어짜피 모든 간선을 탐색해야 하는데 굳이 prique를 써서 사용해야 하나 싶었다.
• 이후, 위상정렬을 이용해 dp로 풀었더니 $O(M+N)$으로 시간을 많이 단축시킬 수 있었다.

 

다익스트라 스타일 ($O(MlogN)$)

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

struct data {
	int dep;
	int cost;
	bool operator<(const data p)const {
		return p.cost > cost;
	}
};
vector<struct data> vec[10'001];
vector<int> _next[10'001];
int _cost[10'001];
bool vi[10'001];
int dap = 0;

void dfs(int p)
{
	vi[p] = 1;
	int size = _next[p].size();
	for (int i = 0; i < size; i++) {
		int tar = _next[p][i];
		dap++;
		if (!vi[tar])dfs(tar);
	}
}

int main()
{
	int n, m, st, en;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		vec[v].push_back({u, w});
	}
	scanf("%d %d", &st, &en);
	priority_queue<struct data> que;
	que.push({ en, 0 });
	while (!que.empty()) {
		struct data cur = que.top();
		que.pop();
		int size = vec[cur.dep].size();
		for (int i = 0; i < size; i++) {
			struct data target = vec[cur.dep][i];
			if (_cost[target.dep] == 0) {
				_cost[target.dep] = cur.cost + target.cost;
				_next[target.dep].push_back(cur.dep);
				que.push({ target.dep, _cost[target.dep] });
			}
			else if(_cost[target.dep] < cur.cost + target.cost) {
				_cost[target.dep] = cur.cost + target.cost;
				_next[target.dep].clear();
				_next[target.dep].push_back(cur.dep);
				que.push({ target.dep, _cost[target.dep] });
			}
			else if (_cost[target.dep] == cur.cost + target.cost) {
				_next[target.dep].push_back(cur.dep);
			}
		}
	}
	printf("%d\n", _cost[st]);
	dfs(st);
	printf("%d\n", dap);

	return 0;
}

 

위상 정렬(DP) ($O(N+M)$)

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

struct data {
	int node;
	int cost;
};
vector<struct data> fwd[10'001], opp[10'001];
int lev[10'001], _cost[10'001];
bool vi[10'001];
int dap = 0;

void dfs(int p)
{
	for (auto& edge : opp[p]) {
		if (_cost[p] == _cost[edge.node] + edge.cost) {
			dap++;
			if (!vi[edge.node]) {
				vi[edge.node] = 1;
				dfs(edge.node);
			}
		}
	}
	return;
}

int main()
{
	int n, m, st, en;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		fwd[u].push_back({ v, w });
		opp[v].push_back({u, w});
		lev[v]++;
	}
	scanf("%d %d", &st, &en);
	queue<int> que;
	que.push(st);
	while (!que.empty()) {
		int cur = que.front();
		que.pop();
		for (auto& edge : fwd[cur]) {
			if (_cost[edge.node] == 0)_cost[edge.node] = _cost[cur] + edge.cost;
			else if (_cost[edge.node] < _cost[cur] + edge.cost) {
				_cost[edge.node] = _cost[cur] + edge.cost;
			}
			lev[edge.node]--;
			if (lev[edge.node] == 0)que.push(edge.node);
		}
	}
	printf("%d\n", _cost[en]);
	dfs(en);
	printf("%d\n", dap);
	return 0;
}