zoj 1655 Transport Goods （Dijkstra）

ZOJ Problem Set - 1655 Transport Goods 

 

结题报告：

一开始用的是从首都向其他城市搜索，记录路径，然后向回搜索，但是出现了wa。

后来搜了一下结题报告，别人都是直接搜索，使费用率最大，试了一下，这样做还是wa

最后看了 小媛 的，才知道是可能同时出现费用率不同的同一条路，这是后我们当然要选择费用率较小的

感觉自己第一遍记录路径代码可以过！，但是细节没有注意

 

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

#define maxn 105
#define INF 1000000000.0
#define MIN 0.000001

double rate[maxn][maxn];//城市间的费用率 
double weight[maxn];//每个城市可以送的物资 
double dist[maxn];
int S[maxn];
int n, m;

void Dijkstra( int v0 )
{
	int i, j;
	for( i = 1; i <= n; i++ )
	{
		dist[i] = rate[v0][i]; S[i] = 0;
	}
	S[v0] = 1; dist[v0] = 1;
	for( i = 1; i < n; i++ )
	{
		double max = -1.0;
		int u = v0;
		for( j = 1; j <= n; j++ )
		{
			if( !S[j] && (dist[j] - max) > MIN )
			{
				u = j; 
				max = dist[j];
			}
		}
		S[u] = 1;
		for( j = 1; j <= n; j++ )
		{
			if( !S[j] && rate[u][j] > MIN && (dist[u]*rate[u][j] - dist[j]) > MIN)
				dist[j] = dist[u]*rate[u][j];
		}
	}
}

int main( )
{
	int i, j, u, v;
	double w, ans;
	while(scanf("%d%d", &n, &m) != EOF )
	{
		ans =0;
		for(i = 1; i < n; i++ )
		{
			scanf("%lf", &weight[i]); 
		}
		for( i = 1; i <= n; i++ )
		{
			for( j = 1; j <= n; j++ )
			{
				rate[i][j] = 0.0;
			}
		}	
		for( i = 1; i <= m; i++ )
		{
			scanf("%d%d%lf", &u, &v, &w);
			if(rate[u][v] < 1.0 - w)
				rate[u][v] = rate[v][u] = (1.0-w);
		}
		Dijkstra( n );
		for( i = 1; i < n; i++ )
		{
			ans += weight[i]*dist[i];
		}
		printf("%.2lf\n", ans);
	}
	return 0;
} 

//没想到最后竟然是可能存在重合的边，但是比率大小不同