Boj 5250) 최단 경로들

문제

백준 5250

설명

시작점과 끝점이 주어지고 어떤 최단경로 \(S\) 가 주어진다. 그리고 최단경로의 간선 각각이 사라졌을 때의 최단경로를 구해야한다.

각 간선이 사라졌을 때마다 다익스트라나 SPFA 를 사용해서 최단경로를 구해도 주어진 조건 상 아슬아슬하게 가능하다고 한다. 하지만 정해는 다음과 같을 것이다.

1. \(S\) 중 간선 하나가 사라졌다면 최단경로는 \(S\) 이외의 간선을 당연히 경유한다.

2. 특정한 간선 \(K\) 을 지나는 최단경로는 시작점과 끝점 각각에서 최단경로로 이루어진 트리 를 구해서 이 둘을 \(K\) 를 이용해 이으면 된다.

3. 이 경로는 \(S\) 와 일부 겹치게 되어, 시작점/끝점 각각마다 마지막으로 \(S\) 와 겹치는 지점이 존재하게 된다.
   • 최단경로의 특성 상 시작점/끝점 부터 \(K\) 겹치다가 갈라지는 경우만 존재하기 때문이다. 다시말해 다시 \(S\) 로 합류하지 않는다.
4. 이는 곧 사라지는 간선에 영향을 받지 않는 범위와 같다. 이를 바탕으로 효율적으로 쿼리하면 된다.

나도 위와 비슷한 발상을 했지만 한군데에서 논리적 비약을 해서 삽질을 해버렸다. 지금부터 내가 한 삽질을 기술하도록 하겠다.

삽질

위에 대해서 나는 간선이 아니라 정점을 중심으로 생각했다. 즉 1번을 \(S\) 이외의 정점을 지난다고 생각했다. 그리고 \(S\) 사이의 간선은 중간에 임시정점을 삽입해서 해결하였다.

여기까지는 괜찮다. 하지만 문제는 2번이다.

임의의 정점을 반드시 지나는 최단경로는 임의의 정점과 시작점/끝점 사이의 최단거리의 합인가?

위 명제는 적어도 나에겐 그럴듯했으나 틀렸다.

예를들어 다음과 같은 반례가 있다.

5 5 5 3
1 2 1
2 3 1
1 4 1
2 4 5
5 1 1
4
5 1 2 3

왜냐하면 최단경로 트리 상의 간선 이외의 간선으로 더 빨리 갈 수 있기 때문이다.

시간 복잡도

O(\(\mathrm{N} \log{\mathrm{M}} + \mathrm{M} \log{\mathrm{N}}\))

• 다익스트라 구현 + 세그구성

코드

template<typename T, size_t _H>
class SegmentTree
{
	template<typename F>
	struct Node {
		Node() {}
		Node(F v) : v(v) {}
		F operator+(const Node& in) { return min(v, in.v); }
		bool Lazy() { return lazy != 1e9; }
		void LazyPropa(F in) { lazy = min(lazy, in); }
		F v = 1e9, lazy = 1e9;
	};
public:
	void Update(int l, int r, T v) { assert(r <= INDEX_MAX); _t1 = l; _t2 = r; _t3 = v; Update_Recursive(1, 1, INDEX_MAX); }
	Node<T> Query(int l, int r) { assert(r <= INDEX_MAX); _t1 = l; _t2 = r; return Query_Recursive(1, 1, INDEX_MAX); }

private:
	void LazyPropa(int x, int s, int e, T v)
	{
		nodes[x].v = min(nodes[x].v, v); 
		if (s != e) {
			nodes[2 * x].LazyPropa(v);
			nodes[2 * x + 1].LazyPropa(v);
		}
	}

	void Update_Recursive(int x, int s, int e)
	{
		if (nodes[x].Lazy()) // 기존에 Lazy 가 있는경우 자식으로 Propa 함
			LazyPropa(x, s, e, nodes[x].lazy);

		if (_t1 <= s && e <= _t2)  // 현재 범위가 업데이트할 범위 내에 있는 경우
			LazyPropa(x, s, e, _t3);
		else if (!(_t2 < s || e < _t1)) {  // 현재 범위가 업데이트할 범위에 걸치는 경우
			int m = (s + e) / 2;
			Update_Recursive(2 * x, s, m);
			Update_Recursive(2 * x + 1, m + 1, e);
			nodes[x] = nodes[2 * x] + nodes[2 * x + 1];
		}
	}

	Node<T> Query_Recursive(int x, int s, int e)
	{
		if (nodes[x].Lazy()) 
			LazyPropa(x, s, e, nodes[x].lazy);

		if (_t2 < s || e < _t1)   return {};
		if (_t1 <= s && e <= _t2) return nodes[x];
		int m = (s + e) / 2;
		return Query_Recursive(x * 2, s, m) + Query_Recursive(x * 2 + 1, m + 1, e);
	}

public:
	Node<T> nodes[1 << _H];
	int INDEX_MAX = 1 << _H - 1;
	int _t1, _t2;
	T _t3;
};

SegmentTree<int, 12> seg;


struct E { int d, w; };
namespace std {

	template<> struct greater<E> {
		bool operator()(const E& a, const E& b) const { return a.w > b.w; }
	};
}

const int MAX_W = 1e9;
const int MAX_IN = 2001;

int n; // vertex number
vector<E> edges[MAX_IN];
int shortPathIdx[MAX_IN];

int s_dp[MAX_IN], e_dp[MAX_IN];
int s_ptb[MAX_IN], e_ptb[MAX_IN];


void Dijkstra(int start, int* dp)
{
	fill(dp, dp + MAX_IN, MAX_W);
	priority_queue<E, vector<E>, greater<E>> q;
	dp[start] = 0; q.push({ start, 0 });

	while (!q.empty())
	{
		E cur = q.top(); q.pop();
		if (dp[cur.d] < cur.w) continue;  // out of updated edge
		for (E& e : edges[cur.d])
			if (dp[cur.d] + e.w < dp[e.d])
			{
				dp[e.d] = dp[cur.d] + e.w;
				q.push({ e.d, dp[e.d] });
			}
	}
}

void DAG(int cur, int spar, int* dp, int* ptb)
{
	if (ptb[cur]) return;
	ptb[cur] = spar = shortPathIdx[cur] ? cur : spar;

	for (E& e : edges[cur])
	{
		if (dp[cur] + e.w != dp[e.d]) continue;
		// 주어진 최단경로가 포함되도록 트리 구성
		if (shortPathIdx[e.d] && !shortPathIdx[cur]) continue;
		DAG(e.d, spar, dp, ptb);
	}
}

int main()
{
	int m, a, b;
	cin >> n >> m >> a >> b;

	for (int i = 0; i < m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		edges[u].push_back({ v, w });
		edges[v].push_back({ u, w });
	}

	int k; vector<int> path;
	cin >> k;
	for (int i = 0; i < k; i++)
	{
		int tmp;
		cin >> tmp;
		path.emplace_back(tmp);
		shortPathIdx[tmp] = i + 1;
	}

	Dijkstra(a, s_dp);
	Dijkstra(b, e_dp);

	DAG(path.front(), path.front(), s_dp, s_ptb);
	DAG(path.back(), path.back(), e_dp, e_ptb);

	for (int i = 1; i <= n; i++)
		for (E& e : edges[i])
		{
			// 주어진 최단거리 상의 간선이면 제외
			if (shortPathIdx[i] && shortPathIdx[e.d] && shortPathIdx[e.d] - shortPathIdx[i] == 1) continue;
			int p1 = shortPathIdx[s_ptb[i]], p2 = shortPathIdx[e_ptb[e.d]];
			int w = e.w + s_dp[i] + e_dp[e.d];
			seg.Update(p1, p2-1, w);
		}

	for (int i = 1; i < k; i++)
	{
		int ans = seg.Query(i, i).v;
		cout << (ans >= MAX_W ? -1 : ans) << '\n';
	}

}