2224.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2224 on 2006-07-23 at 15:50:44 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int NM = 8;
const int SN = 1 << NM;
const int CM = 32;
const double INF = 1e20;

int main()
{
	int n, m, p, src, dis, t[NM], map[CM][CM];
	int i, j, k, l;
	double go[CM][SN];

	while(scanf("%d %d %d %d %d", &n, &m, &p, &src, &dis) != EOF && n != 0) {
		for(i = 0; i < n; i++) scanf("%d", &t[i]);
		memset(map, -1, sizeof(map)); src--; dis--;
		for(i = 0; i < p; i++) {
			int a, b, d; scanf("%d %d %d", &a, &b, &d);
			map[a-1][b-1] = map[b-1][a-1] = d;
		}
		int sm = 1 << n;
		double best = INF;
		for(i = 0; i < m; i++) go[i][sm-1] = INF;
		go[src][sm-1] = 0;
		for(i = sm-2; i >= 0; i--) {
			for(j = 0; j < m; j++) {
				go[j][i] = INF;
				for(k = 0; k < m; k++) {
					if(map[j][k] == -1) continue;
					for(l = 0; l < n; l++)
						if(!(i&(1<<l))) go[j][i] = min(go[j][i], go[k][i|(1<<l)]+1.0*map[j][k]/t[l]);
				}
				if(j == dis) best = min(best, go[j][i]);
			}
		}
		if(best > 1e8) printf("Impossible\n");
		else printf("%.3lf\n", best);
	}
	
	return 0;
}