GONDOR - GONDOR

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<cfloat>
#include<cmath>
#include<queue>
using namespace std;

#define N 100
int x[N], y[N], s[N], n, receive[N][N-1];
double dis[N][N], dp[N];

inline int sqr(int x) { return x*x; }

int main() {
#ifdef __DONGOCKHANH__
	freopen("input.txt", "r", stdin);
#endif
	scanf("%d", &n);
	for(int i = 0; i < n; ++i) {
		scanf("%d%d%d",x+i,y+i,s+i);
		for(int j = 0; j < n - 1; --receive[i][j++])
			scanf("%d", &receive[i][j]);
		dp[i] = DBL_MAX;
	}
	for(int i = 0; i < n; ++i)
		for(int j = i+1; j < n; ++j)
			dis[i][j] = dis[j][i] = sqrt(sqr(x[i] - x[j]) + sqr(y[i] - y[j]));
	priority_queue<pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > qu;
	dp[0] = 0; qu.push(make_pair((double) 0, 0));
	while(!qu.empty()) {
		double du = qu.top().first; int u = qu.top().second; qu.pop();
		//printf("%d %.10lf\n", u+1, du);
		if(du > dp[u]) continue;
		for(int i = 0, cnt = 0; cnt < s[u] && i < n-1; ++i) {
			int v = receive[u][i];
			//printf("v: %d %.10lf %d\n", v+1, dp[v] == DBL_MAX ? -1 : dp[v], cnt);
			if(dp[v] < du) continue;
			if(du + dis[u][v] < dp[v]) qu.push(make_pair(dp[v] = du + dis[u][v], v)); 
			++cnt;
		}
	}
	for(int i = 0; i < n; ++i) printf("%.10lf\n", dp[i]);
	return 0;
}

Download