TTRIP - Tham quan Thành Cổ
Tác giả: hieult
Ngôn ngữ: C++
#pragma comment(linker, "/STACK:16777216")
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000001
#define maxn 2002
#define base 1000000000
#define modunlo 111539786
#define oo 1000000002
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define ull unsigned long long
double const PI=4*atan(1);
using namespace std;
typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
typedef long long int64;
int n, a[105][105], flag[105] = {0}, u = 1, v , kq = 0, MIN;
int main(){
//freopen("input.in","r",stdin);
//freopen("output.out","w",stdout);
scanf("%d",&n);
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++){
scanf("%d",&a[i][j]);
if(!a[i][j]) a[i][j] = oo;
}
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= n; k++){
if(a[j][i] + a[i][k] < a[j][k]){
a[j][k] = a[j][i] + a[i][k];
a[k][j] = a[j][i] + a[i][k];
}
}
flag[1] = 1;
while(true){
v = 0;
MIN = oo;
for(int i = 1; i < n; i++){
if(a[u][i] < MIN && !flag[i]){
v = i;
MIN = a[u][i];
}
}
if(v == 0){
break;
}
else{
kq += a[u][v];
u = v;
flag[u] = 1;
}
}
kq += a[u][n];
printf("%d",kq);
}