[백준 13141번 C/C++] Ignition

 

[백준 13141번 C/C++] Ignition

 

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

 

13141번: Ignition

첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000) 두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100) 시작점

www.acmicpc.net

---

 

 

해결방안

 

그래프 이론
브루트포스 알고리즘
최단 경로
플로이드–워셜  Floyd-Warshall 

---

 

정답코드

 

#include <iostream>
#include <vector>
using namespace std;
 
const int INF = 987654321;
 
int n, m; // n: 정점의 수, m: 간선의 수
 
vector<vector<int>> dist; // Floyd-Warshall. 시작->끝 최단경로 기록
vector<vector<int>> v;	  // 실제 간선
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	cin >> n >> m;
	dist.resize(n + 1, vector<int>(n + 1, INF));
	v.resize(n + 1, vector<int>(n + 1, -1));
 
	// 자기 자신을 연결하는 경우 0으로 기본 설정
	for (int i = 1; i <= n; i++) {
		dist[i][i] = 0;
	}
 
	int a, b, c;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
 
		dist[a][b] = dist[b][a] = min(dist[a][b], c);
 
		v[a][b] = v[b][a] = max(v[a][b], c);
	}
 
	// Floyd-Warshall 최단경로 구하기
	for (int k = 1; k <= n; k++){
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
 
	double answer = INF;
 
	for (int k = 1; k <= n; k++) 
	{
		double longest = 0; // 시작(=k)에서 시작했을때 마지막 간선이 사라지는 시간
 
		for (int i = 1; i <= n; i++) 
		{
			for (int j = 1; j <= n; j++) 
			{
				double remain = 0;
				if (v[i][j] != -1) { // i 정점과 연결되지 않은 경우
					remain = (double)v[i][j] - ((double)dist[k][j] - (double)dist[k][i]);
				}
 
				if (remain > 0) { // 0이상이면 아직 선이 다 불타지 않은 경우다
					longest = max(longest, (remain / 2) + (double)dist[k][j]);
				}
			}
		}
 
		answer = min(answer, longest); // 최초 시작 정점(=k) 기준으로 모든 간선을 태우는 시간 최소값 저장
	}
 
	cout << fixed;
	cout.precision(1);
	cout << answer << "\n";
 
	return 0;
}

 

---