CSES PS - investigation (다익스트라, 위상정렬)

https://cses.fi/problemset/task/1202

볼륨이 크다.

 

<문제설명>

사이클이 허용된 가중치가 있는 방향그래프가 주어진다. 시작점 1에서 끝점 n까지 최소 비용으로 이동할 때, (1)그 비용 (2) 가능한 경로의 수, (3) 가능한 경로 중 가장 적은 간선을 지나치는 경우 그 간선의 수, (4) 가장 많은 간선을 지나는 경우 그 간선의 수.

 

(1),(2),(3),(4)를 모두 구하는 문제

 

<풀이>

(1)은 다익스트라로 풀 수 있고, (2),(3),(4)는 DAG일 때 dp로 풀 수 있는 내용이다. 

 

사이클이 있는 그래프라고 해도 최소비용으로 이동하는 경로는 항상 DAG임이 분명하다. 

 

1. 주어진 그래프에서 유효한 즉, 최소비용 경로에 해당하는 간선들만 남겨서 DAG를 만든다.

  

dist(1~u) + w + dist(v~n) == dist(1~n)인 간선들이 유효한 간선에 해당한다.

 

dist(v~n)에 해당하는 값을 1번부터 시작하는 다익스트라로 처리하기가 까다롭다. (항등식 나옴)

 

1에서 시작하는 최단경로 dist[0]과 n에서 시작하는 최단경로 dist[1] 두 종류를 사용하면 간단하게 해결된다.

 

2. DAG를 위상정렬 순서대로 방문하면서 dp를 처리한다.

 

<코드>

typedef pair<ll, ll> P;
const ll MOD = 1e9 + 7;
const int VMAX = 1e5 + 2;
const int EMAX = 2e5 + 4;
const ll INF = 9e18;

int n, m;
ll dist[2][VMAX], dp[3][VMAX]; //0:소스1  1:소스n
vector<P> adj[2][VMAX]; //0:정방향
vector<int> dag[VMAX];

bool chk[VMAX];
void djikstra(bool t) {
	int st = !t ? 1 : n;
	memset(chk, false, sizeof(chk));
	dist[t][st] = 0;

	priority_queue<P, vector<P>, greater<P>> pq;
	pq.push({ dist[t][st], st });

	while (!pq.empty()) {
		ll u = pq.top().second; pq.pop();
		if (chk[u]) continue;

		chk[u] = true;

		for (P pp : adj[t][u]) {
			ll v = pp.first, w = pp.second;
			if (dist[t][v] > dist[t][u] + w) {
				dist[t][v] = dist[t][u] + w;
				pq.push({ dist[t][v],v });
			}
		}
	}
}

int main() {
	FAST;
	cin >> n >> m;
	for (ll i = 0, u, v, w; i < m; i++) {
		cin >> u >> v >> w;
		adj[0][u].push_back({ v,w });
		adj[1][v].push_back({ u,w });
	}

	fill(&dist[0][0], &dist[1][VMAX], INF);
	djikstra(0); //1에서 시작하는 최단경로 dist[0] 초기화
	djikstra(1); //n에서 시작하는 최단경로 dist[1] 초기화

	int ind[VMAX]{ 0 };
	for (ll u = 1; u <= n; u++) {
		for (P pp : adj[0][u]) {
			ll v = pp.first, w = pp.second;
			if (dist[0][u] + w + dist[1][v] == dist[0][n]) {
				dag[u].push_back(v);
				ind[v]++;
			}
		}
	}

	queue<ll> q;
	q.push(1);
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i <= n; i++) dp[1][i] = INF;
	dp[0][1] = 1, dp[1][1] = dp[2][1] = 0;
	//dp 0: 경로수, 1: 최소도시, 2: 최대도시
	while (!q.empty()) {
		ll u = q.front(); q.pop();
		for (ll v : dag[u]) {
			dp[0][v] = (dp[0][v] + dp[0][u]) % MOD;
			dp[1][v] = min(dp[1][v], dp[1][u] + 1);
			dp[2][v] = max(dp[2][v], dp[2][u] + 1);
			if (--ind[v] == 0) q.push(v);
		}
	}

	cout << dist[0][n] << " ";
	for (int i = 0; i < 3; i++) cout << dp[i][n] << " \n"[i == 2];
}

 

<생각>

일반 방향그래프를 DAG로 강제하여 더 의미있는 값들을 구하는 아이디어를 눈여겨 보자

(dist(1~u) + w + dist(v~n) == dist(1~n)인 간선들이 유효한 간선)