백준 25050 (C++) 최고의 간선

최초 업로드: 2025-08-08 05:12:47

최근 수정 시간: 2025-08-08 05:13:24

게시자: rlatjwls3333

카테고리: 백준

# [Platinum V] 최고의 간선

[문제 링크](https://www.acmicpc.net/problem/25050)

## 문제 설명

정점이 $N$개이고, 간선이 $M$개인 단방향 그래프가 주어집니다. 간선은 입력에서 주어지는 순서대로 $1$번부터 $M$번까지의 번호가 붙어 있습니다.

소영이는 많은 정점 쌍들을 최단 거리로 빠르게 연결하고 있는 간선들이 기특하다는 생각이 들었습니다. 그래서 간선들에 각각 점수를 매긴 뒤, 가장 점수가 높은 간선들에게 최고의 간선 상을 수여하려고 합니다. 간선의 점수는 아래와 같은 방식으로 계산합니다.

<ul>
	<li>어떤 정점 $S$에서 정점 $E$로 가는 최단 경로가 존재한다면, 그 최단 경로에 포함되는 모든 간선은 각각 $1$점을 얻습니다. 모든 정점 쌍에 대해, 경로가 존재한다면 최단 경로가 유일한 데이터만 입력으로 주어집니다.</li>
	<li>만약 정점 $S$에서 정점 $E$로 가는 경로가 존재하지 않는다면, 정점 쌍 $(S, E)$ 에 대해서는 모든 간선이 점수를 받지 못합니다.</li>
	<li>$S \neq E$ 이고 $1 \le S, E \le N$을 만족하는 모든 정점 쌍 $(S, E)$ 에서의 점수 합이 간선의 최종 점수가 됩니다.</li>
</ul>

소영이는 점수가 같은 간선이 여러 개가 있다면, 최고 점수를 기록한 모든 간선들에게 상을 주려고 합니다. 어떤 간선들이 최고의 간선 상을 받게 될지를 구해봅시다.

## 입력

첫 번째 줄에는 두 개의 정수 $N$과 $M$이 공백으로 구분되어 주어집니다. $(2 \le N \le 2 \times 10^3, 1 \le M \le min(N\times (N-1),\ 5 \times 10^3))$

다음 $M$개의 줄에는 $i$ 번째 간선의 시작 정점 $u_i$와 도착 정점 $v_i$, 그리고 간선의 길이 $w_i$가 공백으로 구분되어 주어집니다. 같은 정점 쌍을 연결하는 서로 다른 간선이 존재하지 않고, 시작 정점과 도착 정점이 같은 간선은 주어지지 않습니다. $( 1 \le u_i, v_i \le N, u_i \neq v_i, 1 \le w_i \le 10^9)$

## 출력

첫 번째 줄에는 상을 받게 될 간선의 수를 출력합니다.

두 번째 줄에는 상을 받게 될 간선의 번호를 작은 것부터 순서대로 공백으로 구분하여 출력합니다.

## 풀이
#### 최단경로는 다익스트라를 이용해서 구하면 됩니다. 문제의 조건으로 인해 최단 경로가 트리 형태로 나타날 것이니 각 간선에 더할 점수는 트리dp로 $O(N)$만에 구할 수 있습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll LINF = 0x3f3f3f3f3f3f3f3f;

struct element {
 ll u, v, w, idx;
 bool operator<(const element e) const {
 return w > e.w; // pq
 }
};

int n, m;
int cnt[5000];
ll cost[2000];
vector<vector<element>> conn(2000);

int dfs(int cur) {
    int curCost=1;
    for(auto next:conn[cur]) {
        if(cost[next.v] == cost[cur] + next.w) {
            int nextCost = dfs(next.v);
            cnt[next.idx] += nextCost;
            curCost += nextCost;
        }
    }
    return curCost;
}

void dijkstra(int s) {
 fill(cost, cost+n, LINF);
 priority_queue<element> pq; pq.push({-1, s, 0, -1});
 while(!pq.empty()) {
 auto cur = pq.top(); pq.pop();
 if(cur.w>=cost[cur.v]) continue;
 cost[cur.v] = cur.w;

for(auto next : conn[cur.v]) {
            if(cost[next.v] > cur.w + next.w) {
                pq.push({-1, next.v, cur.w + next.w, next.idx});
            }
        }
    }
    dfs(s);
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 cin >> n >> m;
 for(int i=0;i<m;i++) {
 ll u, v, w; cin >> u >> v >> w;
 conn[u-1].push_back({u-1, v-1, w, i});
 }

for(int i=0;i<n;i++) {
 dijkstra(i);
 }

int maxCnt = *max_element(cnt, cnt+m);
 vector<int> res;
 for(int i=0;i<m;i++) {
 if(maxCnt==cnt[i]) {
 res.push_back(i+1);
 }
 }
 cout << res.size() << '\n';
 for(int e : res) cout << e << ' ';
}
```