CodeVS2602.c

// 不得不说，虽然是个水题，但是还是应该保证内存安全，按照@Yoto Chang的说法。于是我就写了一个内存安全的。

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

double **a;
int *x, *y;

int squared (int x) {
	return x * x;
}

double distance (int a, int b) {
	return sqrt(squared(x[a] - x[b]) + squared(y[a] - y[b]));
}

int main (int argc, char *argv[]) {
	int n, m, i, j, k;
	scanf("%i", &n);
	a = (double **) malloc((n + 2) * sizeof(double *));
	x = (int *) malloc((n + 2) * sizeof(int));
	y = (int *) malloc((n + 2) * sizeof(int));
	for (i = 1; i <= n; ++i) a[i] = (double *) malloc((n + 2) * sizeof(double));
	for (i = 1; i <= n; ++i)
		for (j = 1; j <= n; ++j)
			a[i][j] = 0xfffff;
	for (i = 1; i <= n; ++i) scanf("%i %i", &x[i], &y[i]);
	scanf("%i", &m);
	for (i = 1; i <= m; ++i) {
		scanf("%i %i", &j, &k);
		a[k][j] = a[j][k] = distance(j, k);
	}
	for (k = 1; k <= n; ++k)
		for (i = 1; i <= n; ++i)
			for (j = 1; j <= n; ++j)
				if (a[i][k] + a[k][j] < a[i][j]) a[i][j] = a[i][k] + a[k][j];
	scanf("%i %i", &i, &j);
	printf("%.2lf\n", a[i][j]);
	free(x);
	free(y);
	for (i = 1; i <= n; ++i) free(a[i]);
	free(a);
	return 0;
}