题目描述

要求, 只能做一次贸易， 求得一次贸易的最赚的，最少赚0元。
有的路是双向的， 有的路是单项的

题解

1, 用数组模拟链表来存图。
2，我们枚举所有的从1 到n 的为中点，例如中点为k， 那么我们先spfa求得从1到k的能得到的最小的水晶球的价格，然后再从n到k spfa 求得能得到的最大的水晶球的价格。
3，最后遍历从1到n点为中点时的获利，输出最大值即可

难理解的点:
1 为什么dijkstra不可以：
dijkstra算法，当从队列出来时，这个点的值不可以再次被更新，且此时为最小值。
由此，dijkstra的时间复杂度是可以确定的，每个点的值最多被更新一次。
但是此题由于每个点存的是可以到达此点时，得到的最小的价格， 那么当有点从队列中出来时，还有可能会被更新，所以不能用dijkstra。
2 为什么，不能两次spfa从前到后求得最大最小值?
这个图有的路是单项路， 我们必须保证当k为中点时， 必须从1可以到达k，从n也可以到达k，此时才会计算价值，如果从前到后求，不能保证一定能从n到达k点。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;

ll n, m;
ll w[maxn], h[maxn], rh[maxn], ne[maxn], e[maxn], idx;
ll dmin[maxn], dmax[maxn];
ll q[maxn];
bool st[maxn];

void add(ll h[], ll a, ll b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void spfa(ll *dis,ll start, ll *h, bool flag)
{
    memset(st, 0, sizeof st);
    if(flag) memset(dis , 0x3f, sizeof dmin);
    queue<ll> q;

    q.push(start);
    st[start] = true;
    dis[start] = w[start];

    while(q.size())
    {
        ll t = q.front();
        q.pop();
        st[t] = false;

        for(int i = h[t]; ~i; i = ne[i])
        {
            ll j = e[i];
            if(flag && dis[j] > min(dis[t], w[j]) || !flag && dis[j] < max(dis[t], w[j]))
            {
                if(flag) dis[j] = min(dis[t], w[j]);
                else dis[j] = max(dis[t], w[j]);

                if(!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);

    for(int i = 1; i <= n; i ++)
    {
        cin >> w[i];
    }
    while(m --)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        add(h, a, b), add(rh, b, a);
        if(c == 2) add(rh, a, b), add(h, b, a);
    }

    spfa(dmin, 1,  h, true);
    spfa(dmax, n, rh, false);

    ll res = 0;
    for(int i = 1; i <= n; i ++)
    {
        res = max(dmax[i]-dmin[i], res);
    }

    cout << res << endl;
    return 0;
}