취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25050번 문제인 최고의 간선이다.
문제는 아래 링크를 확인하자.

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

이 문제는 "한 노드에서 다른 모든 노드까지의 최단경로"를 나타내는 트리를 구하고, 그 트리 위에서 DP를 이용해 각 에지의 사용횟수를 계산하는 것을 각 노드마다 반복하는 것으로 해결할 수 있다.

주어진 문제의 제약조건에서 주어지는 그래프의 총 에지 개수가 5000개 이하라는 조건을 확인하자.

dijkstra 알고리즘의 시간복잡도는 O(ElgV)이므로, 각 노드를 출발점으로 각각 하여 dijkstra 알고리즘을 한번씩 적용해보는 시간복잡도는 O(VElgV)가 된다. 이는 이 문제 제약조건 상에서 적당히 큰 V에 대해 Floyd-Warshall 알고리즘의 O(V^3)보다 나은 시간복잡도이며, 문제 해결에 충분한 시간복잡도이다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

int N, M;
vector<pair<int, int>> G[2001]; // {target, weight}

int edgeidx[2001][2001], edgeweight[2001][2001];

ll dist[2001];
vector<int> GG[2001];
void dijkstra(int s) {
	priority_queue<pair<ll, pair<int,int>>> pq; // {-d, {par, cur}}
	pq.push(make_pair(0, make_pair(0, s)));

	while (!pq.empty()) {
		ll d = -pq.top().first; int par = pq.top().second.first, cur = pq.top().second.second;
		pq.pop();
		if (dist[cur] < d) continue;

		GG[par].emplace_back(cur);

		for (auto& p : G[cur]) {
			int target = p.first; ll disttmp = d + p.second;
			if (disttmp < dist[target]) {
				dist[target] = disttmp;
				pq.push(make_pair(-disttmp, make_pair(cur, target)));
			}
		}
	}
}

int ans[5001];

int dfs(int cur) {
	int ret = 1;
	for (auto& x : GG[cur]) {
		int tmp = dfs(x);
		ans[edgeidx[cur][x]] += tmp;
		ret += tmp;
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	for (int m = 1; m <= M; m++) {
		int x, y, w; cin >> x >> y >> w;
		if (edgeweight[x][y] == 0 || w < edgeweight[x][y]) {
			edgeweight[x][y] = w;
			edgeidx[x][y] = m;
			G[x].emplace_back(make_pair(y, w));
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int i = 1; i <= N; i++) dist[i] = 1000000000000000007LL, GG[i].clear();
		dist[i] = 0;
		dijkstra(i);
		dfs(i);
	}

	int mx = -1;
	vector<int> vec;
	for (int m = 1; m <= M; m++) {
		if (ans[m] > mx) {
			mx = ans[m];
			vec.clear();
			vec.emplace_back(m);
		}
		else if (ans[m] == mx) vec.emplace_back(m);
	}

	cout << vec.size() << '\n';
	for (auto& x : vec) cout << x << ' ';
}