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;
}

Download