백준 문제풀이

백준 17182번 - C++

diligent_gideok 2022. 6. 3. 20:08
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int v[12][12];

int n, start;
int a, b, c;
int ans=INF;


int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> start;
	for (int i = 1; i <= n; i++)
		fill(v[i], v[i] + 1 + n, INF);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin>>v[i][j];
		}
	}
	for (int i = 0; i < n; i++) v[i][i] = 0;

	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				v[i][j] = min(v[i][j], v[i][k] + v[k][j]); // if 문으로 바꾸면 시간을 줄일 수 있다.


	int a[10];
	for (int i = 0; i < n; i++) {
		if (i == start) a[i] = INF;
		a[i] = i;
	}
	do {
		int st = start;
		int flag = 0;
		for (int i = 0; i < n; i++) {
			if (a[i] == start) continue;
			flag += v[st][a[i]];	
			st = a[i];
			
		}
		ans = min(ans, flag);
	} while (next_permutation(a, a + n));

	cout << ans;
}

'백준 문제풀이' 카테고리의 다른 글

백준 11779번 - C++  (0) 2022.06.06
백준 1753번 - C++  (0) 2022.06.06
백준 21940번 - C++  (0) 2022.06.03
백준 14938번 - C++  (0) 2022.06.03
백준 11780번 - C++  (0) 2022.06.03