백준 12956 (C++) 퍼레이드

최초 업로드: 2025-07-07 21:30:00

최근 수정 시간: 2025-07-25 08:45:34

게시자: rlatjwls3333

카테고리: 백준

# [Gold I] 퍼레이드

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

## 문제 설명

N개의 교차로와 M개의 거리로 이루어진 도시가 있다. 교차로는 0번부터 N-1번까지 번호가 매겨져 있고, 도로는 0번부터 M-1번까지 번호가 매겨져 있다. 모든 도로는 양방향이며, 도로는 서로 다른 교차로를 연결한다. 임의의 두 교차로는 최대 1개의 도로로 연결되어 있다. 모든 교차로는 연결되어 있기 때문에, 한 교차로에서 다른 교차로로 도로를 이용해서 항상 갈 수 있다.

도시의 시장은 퍼레이드를 개최하려고 한다. 퍼레이드는 도로 하나에서 열린다.

도시에는 모든 교차로의 쌍(X, Y) 마다 X와 Y를 오가는 버스가 존재한다. 퍼레이드는 버스의 운행에 영향을 줄 수 있다. 버스가 퍼레이드에 영향을 받는 경우는 퍼레이드에 사용하는 도로를 제외하고 구한 최단 거리의 길이가 제외하지 않고 구한 X에서 Y로 가는 최단 경로의 길이보다 큰 경우이다. 퍼레이드 때문에 X에서 Y로 갈 수 없게 되는 경우도 영향을 받는 경우이다.

각 도로에서 퍼레이드를 개최한다고 했을 때, 영향을 받는 버스 노선의 수가 몇 개인지 구하는 프로그램을 작성하시오.

## 입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 100)과 도로의 개수 M (1 ≤ M ≤ 2,000)이 주어진다.

둘째 줄부터 M개의 줄에는 도로의 정보가 0번 도로부터 순서대로 주어진다.

도로의 정보는 from, to, time으로 이루어져 있으며, from과 to를 오가는데 걸리는 시간이 time이라는 뜻이다. (0 ≤ from, to ≤ N-1, 1 ≤ time ≤ 1,000, from ≠ to)

## 출력

각 도로에서 퍼레이드가 열린다고 했을 때, 영향을 받는 버스 노선의 개수를 0번 도로부터 순서대로 공백으로 구분해 출력한다.

## 풀이
#### 플루이드-와샬 알고리즘을 m+1번 사용하여 풀었다.

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

const int INF = 0x3f3f3f3f;

int n, m;
int minT[100][100], original[100][100];

struct edge {
    int a, b, c;
};

vector<edge> edges(2000);

void floyd(int limit) {
 fill(&minT[0][0], &minT[99][100], INF);
 for(int i=0;i<m;i++) {
 if(i!=limit) {
 minT[edges[i].a][edges[i].b] = min(minT[edges[i].a][edges[i].b], edges[i].c);
 minT[edges[i].b][edges[i].a] = min(minT[edges[i].b][edges[i].a], edges[i].c);
 }
 }
 for(int m=0;m<n;m++) {
 for(int s=0;s<n;s++) {
 for(int e=0;e<n;e++) {
 minT[s][e] = min(minT[s][e], minT[s][m] + minT[m][e]);
 }
 }
 }
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 cin >> n >> m;
 for(int i=0;i<m;i++) cin >> edges[i].a >> edges[i].b >> edges[i].c;

floyd(-1);
    memcpy(original, minT, sizeof minT);

for(int i=0;i<m;i++) {
 floyd(i);
 int cnt=0;
 for(int j=0;j<n;j++) {
 for(int k=j+1;k<n;k++) {
 if(original[j][k] != minT[j][k]) cnt++;
 }
 }
 cout << cnt << ' ';
 }
}
```