【NOIP2009提高组】最优贸易

https://www.luogu.org/problem/show?pid=1073

如果他想在i点卖出，那么就要在从1点出发到i点的路径里找个最便宜的买入，用Bellman-Ford求出这样最便宜的买入价记为minp[i]。他能获得的利润就是price[i]-minp[i]。

但是并不是可以在所有的点都可以卖出，因为他最终要走到N，所以只有在和N联通的点才能卖出。用从N点出发倒着的DFS/BFS记录点i是否能到达N点。

故答案为max{price[i]-minp[i] (i点与N点联通)}

#include <iostream>

#include <vector>

#include <queue>

#define maxn 100005

using namespace std;

const int inf = ;

int n, m, price[maxn];

vector<int> g[maxn], gt[maxn];

int minp[maxn];

bool inque[maxn];

queue<int> q;

void bellman_ford()

{

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

        minp[i] = inf;

    minp[] = price[];

    q.push();

    inque[] = true;

    while (!q.empty())

    {

        int v = q.front();

        q.pop();

        inque[v] = false;

        for (int i = ; i < g[v].size(); i++)

        {

            int w = g[v][i];

            if (minp[w] > min(minp[v], price[w]))

            {

                minp[w] = min(minp[v], price[w]);

                if (!inque[w])

                {

                    inque[w] = true;

                    q.push(w);

                }

            }

        }

    }

}

bool avai[maxn];

void dfs(int v)

{

    avai[v] = true;

    for (int i = ; i < gt[v].size(); i++)

    {

        int w = gt[v][i];

        if (!avai[w])

            dfs(w);

    }

}

int main()

{

    ios::sync_with_stdio(false);

    cin >> n >> m;

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

        cin >> price[i];

    int u, v, z;

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

    {

        cin >> u >> v >> z;

        g[u].push_back(v);

        gt[v].push_back(u);

        if (z == )

        {

            g[v].push_back(u);

            gt[u].push_back(v);

        }

    }

    bellman_ford();

    dfs(n);

    int ans = ;

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

    {

        if (avai[i])

            ans = max(ans, price[i] - minp[i]);

    }

    cout << ans << endl;

    return ;

}