学步园

大意不再赘述。

思路：比较简单，我们可以手推一下，离源点最近的顶点直接将货物运到汇点与等待所有货物到达某一城市再送去汇点的消耗量是一样的。于是我们可以求一次最长路径，只不过更新的条件变了一下，即求汇点要每个顶点的最高的保存率（1-c），然后与每个城市储存的货物重量相乘，这样我们就可以去求解了。

这是双向图，有重边时，我们选择保存率更高的存下。

CODE：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
using namespace std;

const int MAXN = 110;
const int INF = 0x3f3f3f3f;

double w[MAXN][MAXN], d[MAXN];
double weight[MAXN];
bool vis[MAXN];

int n, m;

void init(int src)
{
	memset(w, 0, sizeof(w));
	memset(vis, 0, sizeof(vis));
}

void Dijkstra(int src)
{
	for(int i = 1; i <= n; i++) d[i] = (i == src)? 1:0; //置源点未消耗率为1 
	for(int i = 1; i <= n; i++)
	{
		int x;
		double m = -INF;
		for(int y = 1; y <= n; y++) if(!vis[y] && m < d[y]) m = d[x=y];
		vis[x] = 1;
		for(int y = 1; y <= n; y++) if(!vis[y])
		{
			d[y] = max(d[y], d[x] * w[x][y]);
		}
	}
}

int main()
{
	while(~scanf("%d%d", &n, &m))
	{
		init(n);
		for(int i = 1; i < n; i++) scanf("%lf", &weight[i]);
		while(m--)
		{
			int u, v;
			double c;
			scanf("%d%d%lf", &u, &v, &c);
			if(w[u][v] < 1-c) //判重边 
			{	
				w[u][v] = w[v][u] = 1-c;
			}
		}
		Dijkstra(n);
		double ans = 0;
		for(int i = 1; i < n; i++) ans += d[i] * weight[i];
		printf("%.2lf\n", ans); 
	}
	return 0;
}