TTRIP - Tham quan Thành Cổ
Tác giả: ll931110
Ngôn ngữ: C++
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
int n,a[105][105];
int INF = (1 << 30) - 5;
bool check[105];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
scanf("%d", &a[i][j]);
if (i != j && !a[i][j]) a[i][j] = INF;
}
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
a[i][j] = min(a[i][j],a[i][k] + a[k][j]);
int ret = 0,start = 0;
for (int iter = 0; iter < n - 2; iter++) {
int len = INF,pos;
for (int j = 1; j < n - 1; j++) if (!check[j] && a[start][j] < len) {
len = a[start][j];
pos = j;
}
ret += len;
check[pos] = true;
start = pos;
}
printf("%d\n", ret + a[start][n - 1]);
}