2047.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2047 on 2006-07-23 at 15:48:15 */ 
#include <cstdio>
#include <cstring>
#include <cmath>

const int MAX = 128;
const double INF = 2000000;
const double eps = 1e-6;

double pro[MAX][MAX];

inline double percent(const double);
inline double parse(const double);
double Dijkstra(int, int);

int main()
{
	int n, m, i, j;
	
	while(scanf("%d %d", &n, &m) != EOF && n != 0) {
		for(i = 0; i < n; i++) {
			pro[i][i] = 0;
			for(j = i+1; j < n; j++) {
				pro[j][i] = pro[i][j] = INF;
			}
		}
		for(i = 0; i < m; i++) {
			int a, b;
			double d;
			scanf("%d %d %lf", &a, &b, &d);
			pro[a-1][b-1] = pro[b-1][a-1] = percent(d);
		}
		printf("%.6lf percent\n", parse(Dijkstra(0, n)));
	}
	
	return 0;
}

inline double percent(const double n)
{
	return -log10(n/100);
}
inline double parse(const double n)
{
	return 100 * pow(10, -n);
}
double Dijkstra(int src, int n)
{
	const int dis = n - 1;
	int i, j, mini;
	double d[MAX];
	bool visit[MAX] = { false };
	for(i = 0; i < n; i++) {
		d[i] = INF;
	}
	d[src] = 0;
	for(i = 0; i < n; i++) {
		double min = INF;
		for(j = 0; j < n; j++) {
			if(!visit[j] && min - d[j] > eps) min = d[j], mini = j;
		}
		if(mini == dis) break;
		if(fabs(min-INF) < eps) return INF;
		else {
			visit[mini] = true;
			for(j = 0; j < n; j++) {
				if(d[j] - (d[mini] + pro[mini][j]) > eps) {
					d[j] = d[mini] + pro[mini][j];
				}
			}
		}
	}
	return d[dis];
}