TTRIP - Tham quan Thành Cổ
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 111;
typedef pair<int, int> ii;
priority_queue<ii, vector<ii>, greater<ii> > a[N];
int n, c[N][N], vst[N];
void enter() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
scanf("%d",&c[i][j]), c[i][j] = c[i][j] == 0 ? 1000000000 : c[i][j];
}
void floyd() {
for(int k = 1; k <= n; ++k)
for(int u = 1; u <= n; ++u)
for(int v = 1; v <= n; ++v)
c[u][v] = min(c[u][k] + c[k][v], c[u][v]);
}
void solve() {
for(int u = 1; u <= n; ++u)
for(int v = 1; v < n; ++v)
a[u].push(ii(c[u][v], v));
int res = 0, u = 1;
while(true) {
vst[u] = 1; while(!a[u].empty() && vst[a[u].top().second]) a[u].pop();
if(a[u].empty()) { res += c[u][n]; break; }
else {
int v = a[u].top().second;
res += a[u].top().first; a[u].pop(); u = v;
}
}
printf("%d\n", res);
}
int main() {
enter();
floyd();
solve();
return 0;
}