TTRIP - Tham quan Thành Cổ
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cstdio>
#define oo 1000111222
using namespace std;
int n,x,d[111][111],visited[111];
long long ans;
int main()
{
cin >> n;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
scanf("%d",&d[i][j]);
if (!d[i][j]) d[i][j]=oo;
}
for (int k=1;k<=n;k++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
visited[x=1]=1;
while (1)
{
int y=0,best=oo-1;
for (int i=2;i<n;i++)
if (!visited[i] && d[x][i]<best)
best=d[x][i], y=i;
if (!y) break;
ans+=d[x][y]; visited[x=y]=1;
}
ans+=d[x][n];
cout << ans << endl;
}