2472.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Memory:148K  Time:78MS
Language:C++  Result:Accepted

Source 

#include"iostream.h"
#include"stdio.h"
#include"math.h"

const int size=100;
typedef double type;

type e[size][size];

////////////////////////////////////////////////////////////////////////////////////////////////
//	dijstra	连通返回1，否则返回0；
//	strat	源点；
//	e		边权矩阵；
//	ans		返回到各点的最短距离；

bool dijstra(int start,int n,type e[size][size],type ans[size])
{
	const type max=99999999;

	int i,j,k;
	type dis[size],temp;
	bool reach[size];

	for(i=0;i<n;i++)
		reach[i]=false,dis[i]=max;

	dis[start]=0;

	for(i=0;i<n;i++)
	{
		k=-1;
		for(j=0;j<n;j++)
		{
			if(	!reach[j]	//dijstra 
				&&(k<0||dis[k]>dis[j]))
				k=j;
		}

		if(k<0)break;

		reach[k] = true;

		for(j=0;j<n;j++)
		{
			temp=dis[k]+e[k][j];
			
			if(dis[j]>temp)
				dis[j]=temp;
		}
	}

	for(j=0;j<n;j++)
		ans[j]=dis[j];

	return k>=0;
}


///////////////////////////////////////////////////////////////////////
int n,m;

bool init()
{
	int i,j,a,b;
	double c;

	cin>>n;
	
	if(n==0)		return 0;

	cin>>m;

	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
		e[i][j]=1e10;

	for(i=0;i<m;i++)
	{
		cin>>a>>b>>c;
		e[a-1][b-1]=-log(c/100)<e[a-1][b-1]?-log(c/100):e[a-1][b-1];
		e[b-1][a-1]=e[a-1][b-1];
	}
	
	return 1;
}

int main()
{
	double dis[100];
	while(init())
	{
		dijstra(0,n,e,dis);
		printf("%.6lf percent\n",exp(-dis[n-1])*100);
	}

	return 0;
}