BOJ 1162 - 도로포장 (다익스트라)

https://www.acmicpc.net/problem/1162

정점의 상태를 잘 정의하고 정의된 정점 간의 간선이 어떻게 이어져있는지를 잘 파악하면 된다.

 

 

<문제설명>

양방향 가중치 그래프가 주어진다. 연결된 간선에 대해서 최대 k번 가중치를 0으로 만들 수 있을 때, 정점 1에서 정점n으로 가는 최단길이는?

 

<풀이>

u번 정점 전까지 도로포장을 t번했다면 정점을 (u,t)로 정의한다 (정점의 상태가 최대 20개라서 가능)

u->v에 대해 (u,t) -> (v,t), (v,t+1) .. t+1<=k 이다.

 

최대정점 수는 도시수*20 = 2e5이다. -> 다익스트라로 풀 수 있다.

 

<코드>

typedef pair<ll, ll> P;
typedef pair<ll, P> T;
const int MAX = 1e4 + 2;
const ll INF = 1e18;

vector<P> adj[MAX];
ll dist[MAX][21];

int main() {
	FAST;
	ll n, m, k; cin >> n >> m >> k;
	fill(&dist[0][0], &dist[MAX - 1][21], INF);
	dist[1][0] = 0;
	for (ll i = 0, u, v, w; i < m; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({ v,w });
		adj[v].push_back({ u,w });
	}

	bool chk[MAX][21]{ 0 };
	priority_queue<T, vector<T>, greater<T>> pq; //dist, (정점)
	pq.push({ dist[1][0], {1,0} });
	
	while (!pq.empty()) {
		P pp = pq.top().second; pq.pop();
		ll curr = pp.first, t = pp.second; 
		if (chk[curr][t]) continue; //정점이 2차원으로 표현되므로 체크도 2차원
		chk[curr][t] = true;

		//모든 인접한 정점에 대해
		for (P p : adj[curr]) {
			ll next = p.first, d = p.second;
			if (t <= k - 1) {
				if (dist[next][t + 1] > dist[curr][t]) {
					dist[next][t + 1] = dist[curr][t];
					pq.push({ dist[next][t + 1],{next,t + 1} });
				}
			}
			if (dist[next][t] > dist[curr][t] + d) {
				dist[next][t] = dist[curr][t] + d;
				pq.push({ dist[next][t],{next,t} });
			}
		}
	}


	ll ans = INF;
	for (int i = 0; i <= k; i++) ans = min(ans, dist[n][i]);
	cout << ans << '\n';
}