1763.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/* This Code is Submitted by wywcgs for Problem 1763 on 2006-11-08 at 13:39:21 */
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
const int MAX = 512;
const int N_MAX = 32;
const int F_MAX = 128;
const int INF = 100000000;
typedef pair<int, int> pii;
 
class Heap {
private:
	int size;
	int p[MAX], d[MAX], h[MAX];
	void siftUp(int);
	void siftDown(int);
public:
	void clear(int);
	bool isEmpty();
	void push(int, int);
	pii pop();
};
void Heap::siftUp(int n) {
	int dn = d[n], pn = p[n];
	int i = n;
	while(i > 0 && dn < d[(i-1)/2]) {
		d[i] = d[(i-1)/2];
		p[i] = p[(i-1)/2];
		h[p[i]] = i;
		i = (i - 1) / 2;
	}
	d[i] = dn;
	p[i] = pn;
	h[pn] = i;
}
void Heap::siftDown(int n) {
	int dn = d[n], pn = p[n];
	int i = n;
	while(2 * i + 2 <= size) {
		int m = 2 * i + 1;
		if(m + 1 < size && d[m] > d[m+1]) {
			m++;
		}
		if(dn > d[m]) {
			d[i] = d[m];
			p[i] = p[m];
			h[p[i]] = i;
			i = m;
		} else {
			break;
		}
	}
	d[i] = dn;
	p[i] = pn;
	h[pn] = i;
}
void Heap::clear(int n) {
	size = 0;
	int i;
	for(i = 0; i < n; i++) {
		h[i] = -1;
	}
}
bool Heap::isEmpty() {
	return (size == 0);
}
void Heap::push(int s, int t) {
	if(h[s] == -1) {
		h[s] = size++;
		d[h[s]] = t;
		p[h[s]] = s;
		siftUp(h[s]);
	} else if(h[s] == -2 || d[h[s]] <= t) {
		return;
	} else {
		d[h[s]] = t;
		siftUp(h[s]);
	}
}
pii Heap::pop() {
	pii b = pii(p[0], d[0]);
	h[p[0]] = -2;
	if(--size != 0) {
		d[0] = d[size];
		p[0] = p[size];
		h[p[0]] = 0;
		siftDown(0);
	}
	return b;
}
 
class Inter {
public:
	int nei[N_MAX], neil[N_MAX];
	int n, o;
	void link(Inter&, int);
};
void Inter::link(Inter& c, int d) {
	nei[n] = c.o;
	c.nei[c.n] = o;
	neil[n++] = c.neil[c.n++] = d;
}
 
int city[MAX][MAX];
Inter inter[MAX];
int n;
 
void dijkstra(int);
 
int main()
{
	int i, j;
	int fire[F_MAX], f;
	char line[N_MAX];
	int a, b, d;
	
	for(i = 0; i < MAX; i++) {
		inter[i].o = i;
	}
	while(scanf("%d %d", &f, &n) != EOF) {
		for(i = 0; i <= n; i++) {
			inter[i].n = 0;
		}
		for(i = 0; i < f; i++) {
			scanf("%d", &fire[i]);
			getchar();
		}
		while(gets(line) != NULL && sscanf(line, "%d %d %d", &a, &b, &d) == 3) {
			inter[a].link(inter[b], d);
		}
		for(i = 1; i <= n; i++) {
			dijkstra(i);
		}
		int sat[MAX];
		for(i = 1; i <= n; i++) {
			sat[i] = INF;
			for(j = 0; j < f; j++) {
				if(sat[i] > city[i][fire[j]]) {
					sat[i] = city[i][fire[j]];
				}
			}
		}
		int best = 0, bl = INF;
		for(i = 1; i <= n; i++) {
			int m = 0;
			for(j = 1; j <= n; j++) {
				d = min(city[i][j], sat[j]);
				m = max(m, d);
			}
			if(m < bl) {
				bl = m;
				best = i;
			}
		}
		printf("%d\n", best);
	}
	
	return 0;
}
 
void dijkstra(int src)
{
	int i;
	Heap heap;
	
	heap.clear(n+1);
	heap.push(src, 0);
	while(!heap.isEmpty()) {
		pii in = heap.pop();
		int o = in.first;
		city[src][o] = in.second;
		for(i = 0; i < inter[o].n; i++) {
			heap.push(inter[o].nei[i], in.second+inter[o].neil[i]);
		}
	}
}