ZOJ-1655 Transport Goods---dijkstra变形&&最长路

题目链接：

题目大意：

有N-1个城市给首都(第N个城市)支援物资，有M条路，走每条路要耗费一定百分比的物资。问给定N-1个城市将要提供的物资，和每条路的消耗百分比。求能送到首都的最多的物资数量

思路：

由于每条路有费用率，比如1-2路的费用率是0.2，2-3的费用率是0.3，那么x质量的物品经1-3只剩下x*(1-0.2)*(1-0.3)，一开始弄错了，以为消耗的是X*0.2*0.3，用最短路求，这显然是错误的，因为在路上消耗的不能算成费用率的乘积，比如之前的例子，在路上消耗的应该是x*0.2 + x*(1-0.8)*0.3,而直接计算剩余的，就可以用乘积的形式x*(1-0.2)*(1-0.3),所以直接将Map存为剩余率（1-费用率），而且数据中存在重边，所以要保存剩余率最大的那条边，然后用dijkstra求最长路，最长的话也是可dijkstra最短路思想一样，只是找出离源点的最短点变成离源点的最长点，更新dist时也是往大的更新，dist初始化时应该初始化成0。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<stack>

 #include<map>

 #include<set>

 #include<sstream>

 #define MEM(a, b) memset(a, b, sizeof(a));

 using namespace std;

 typedef long long ll;

 const int maxn =  + ;

 const int INF = 0x3f3f3f3f;

 int T, n, m, cases, tot;

 int w[maxn];

 double Map[maxn][maxn];

 double d[maxn];//d[i]表示从源点到i的最大剩余率，由于是无向图，所以也是i到源点的最大剩余率

 bool v[maxn];

 void dijkstra(int u)

 {

     for(int i = ; i <= n; i++)d[i] = ;//初始化成最小的

     d[u] = ;

     memset(v, , sizeof(v));

     for(int i = ; i < n; i++)

     {

         int x;

         double m = ;//这里是double！！！因为这个点一直WA

         for(int i = ; i <= n; i++)if(!v[i] && d[i] - m > 1e-)m = d[x = i];//这里改成找最大值

         v[x] = ;

         for(int i = ; i <= n; i++)

         {

             if(!v[i] && Map[x][i] >= )d[i] = max(d[i], d[x] * Map[x][i]);//松弛操作变成更新为最大值

         }

     }

 }

 int main()

 {

     while(cin >> n >> m)

     {

         for(int i = ; i < n; i++)cin >> w[i];

         for(int i = ; i <= n; i++)

             for(int j = ; j <= n; j++)Map[i][j] = ;

         int u, v;

         double c;

         while(m--)

         {

             cin >> u >> v >> c;

             Map[u][v] = Map[v][u] = max(1.0 - c, Map[u][v]);//有重边！！！

         }

         dijkstra(n);

         double ans = ;

         for(int i = ; i < n; i++)

         {

             ans = ans + 1.0 * w[i] * d[i];

         }

         printf("%.2f\n", ans);

     }

     return ;

 }