https://www.acmicpc.net/problem/10971
10971번: 외판원 순회 2
첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j
www.acmicpc.net
흠 실버 치고 조금 난이도가 있네요
비용이 싼순서로 바로 탐색하는게 아니라 모든 경로를 탐색해서 그합이 가장 낮은걸 찾는게 key point네요
#include <iostream>
#include <vector>
#include <algorithm>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<bitset>
#include<cmath>
using namespace std;
void Prints(vector<vector<char>>maps, int r, int c) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << maps[i][j]<< ",";
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<bool>>maps, int r, int c) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << maps[i][j]<< ",";
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<int>>maps, int r, int c) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << maps[i][j]<<",";
}
cout << endl;
}
cout << endl;
}
struct Point {
int s;
int e;
int cnt;
};
struct Data {
int index;
vector<bool> bVisitied;
int cnt=0;
int gc = 1;
};
int main() {
int n;
vector<vector<int>>maps;
cin >> n;
for (int i = 0; i < n; i++) {
vector<int>tmpMaps;
for (int j = 0; j < n; j++) {
int tmp;
cin >> tmp;
tmpMaps.push_back(tmp);
}
maps.push_back(tmpMaps);
}
//Prints(maps, n, n);
//0 1 2 3
vector<bool>bVisitied(n, false);
vector<int>vGsum;
int gsum = 0;
for (int z = 0; z < n; z++) {
int gStart = 0;
int gEnd = 0;
int count = 0;
queue<Data>q;
Data p;
p.index = z;
p.bVisitied = bVisitied;
gStart = z;
q.push(p);
int sum = 0;
while (!q.empty()) {
Data start=q.front();
q.pop();
count++;
int max = 1e9;
int arrvie = start.index;
for (int j = 0; j < n; j++) {
if (start.index != j) {
if (start.bVisitied[j]==false&&maps[start.index][j]!=0&&j!=gStart) {
max=maps[start.index][j];
arrvie = j;
sum += max;
bVisitied[j] = true;
Data tmpD;
tmpD.index = arrvie;
tmpD.cnt = start.cnt + maps[start.index][j];
tmpD.gc = start.gc + 1;
start.bVisitied[j] = true;
tmpD.bVisitied = start.bVisitied;
start.bVisitied[j] = false;
gEnd = arrvie;
q.push(tmpD);
}
else if (start.gc==n&&j==gStart&& maps[start.index][j] != 0&& start.bVisitied[j] == false) {
max = maps[start.index][j];
arrvie = j;
if (gsum == 0) {
gsum = start.cnt + maps[start.index][j];
}
else {
if (gsum > start.cnt + maps[start.index][j]) {
gsum = start.cnt + maps[start.index][j];
}
}
sum += max;
bVisitied[j] = true;
Data tmpD;
tmpD.index = arrvie;
tmpD.cnt = start.cnt + maps[start.index][j];
tmpD.gc = start.gc + 1;
start.bVisitied[j] = true;
tmpD.bVisitied = start.bVisitied;
start.bVisitied[j] = false;
gEnd = arrvie;
q.push(tmpD);
}
}
}
}
}
cout << gsum;
return 0;
}