대엉코딩

www.acmicpc.net/problem/11404

1. 풀이방법

- 문제를 읽다보면 문제에서는 버스, 즉 간선(단방향)이 비용(가중치)를 각각 가지고 있다.

- (->BFS로는 구할 수 없겠구나 ! 라는 생각)

- 다익스트라 또는 플로이드 워셜 (대표적)

- 근데 출력을 보니 모든 도시에서 자신을 제외한 모든 점까지의 최단거리를 출력하는 문제 (자신 또는 못가는 경우 0 )

- (-> 플로이드 워셜 ! )

2. 주의사항

- 구현 시 도시사이의 거리를 입력 받기전 가장 큰 값으로 초기화 해줘야 하는데 COST가 100,000을 넘지 않는 다는 말을

- 보고 100001으로 정의해두었다가(INF) 계쏙 98퍼에서 오류가 뜨길래...생각해보니...

- 거쳐서 가는경우 100,000을 그냥 넘을 수 있다는 것......!!! 주의주의.... 그래서 그냥 987654321로 초기화 하였다

3. 나의코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define INF 987654321

int n, m;
int CityToCity[101][101];

void inputs() { //입력함수
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) { //초기화
			if (i == j) continue;
			CityToCity[i][j]=INF;
		}
	}
	int start, end, cost;
	for (int i = 0; i < m; i++) {
		cin >> start >> end >> cost;
		if (CityToCity[start][end] > cost) {
			CityToCity[start][end] = cost;
		}
	}
}

void Searchmin() {
	for (int a = 1; a <= n; a++) {
		for (int b = 1; b <= n; b++) {
			for (int c = 1; c <= n; c++) {
				if (CityToCity[b][a] != INF && CityToCity[a][c] != INF) { //거쳐서 갈 수 있는 경우
					CityToCity[b][c] = min(CityToCity[b][c], (CityToCity[b][a] + CityToCity[a][c]));
				}
			}
		}
	}
}
void outputs() { //출력함수
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (CityToCity[i][j] == INF||i==j)  cout << 0 << " "; 
			else cout << CityToCity[i][j] << " ";
		}
		cout << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputs();
	Searchmin();
	outputs();
	return 0;
}