341. 最优贸易

思路

求出：

  • 从 1 到 i 的过程中，买入的最低价格 dmin[i]
  • 从 i 到 n 的过程中，卖出的最高价格 dmax[i]

等价于求出 $\{dmax[i] - dmin[i]\}, i \in 1,2,\cdots ,n$

只能使用SPFA，因为环的存在

为了保证若1能到i，i必须也能到n，所以分开计算而不是使用一个数组。

为了方便，dmin用正向边，dmax用反边求解。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010, M = 2000010;
int h[N], rh[N], e[M], ne[M], idx;
int p[N];
int dmin[N], dmax[N];
bool st[N];
int n, m;

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

void spfa(int *d, int *h, bool flag, int s){
    queue<int> q;
    memset(st, false, sizeof(st));
    if(flag) memset(d, 0x3f, sizeof(dmin));
    q.push(s);
    st[s] = true;
    d[s] = p[s];

    while(q.size()){
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            if(flag && d[j] > min(d[t], p[j]) || !flag && d[j] < max(d[t], p[j])){
                if(flag) d[j] = min(d[t], p[j]);
                else d[j] = max(d[t], p[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 >> p[i];
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        add(h, a, b);
        add(rh, b, a);
        if(c == 2){
            add(h, b, a);
            add(rh, a, b);
        }
    }
    spfa(dmin, h, true, 1);
    spfa(dmax, rh, false, n);
    
    int res = 0;
    for(int i = 1; i <= n; i++) res = max(res, dmax[i] - dmin[i]);
    cout << res << endl;
    
    return 0;
}