题解 P1073 【最优贸易】

· · 题解

此题可以用SPFA加DP 我DP方法是计算差价，我们跑SPFA时计算最大的差价即可

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

const int N = 100010, M = 500010, MIN = -((1<<30)-1);
struct edge {
    int v, next;
} e[M<<1];
queue<int> q;
int n, m, w[N];
int count, head[N], ans[N];
bool vis[N];
void init() {
    int i;
    memset(head, -1, sizeof(head));
    for (i = 1; i <= n; i++)
        ans[i] = MIN;
    return ;
}

void add(int a, int b) {
    e[++count].v = b;
    e[count].next = head[a];
    head[a] = count;
    return ;
}

void spfa(int s) {
    ans[s] = 0;
    q.push(s);
    vis[s] = true;
    while (!q.empty()) {
        int i, u = q.front();
        q.pop();
        vis[u] = false;
        for (i = head[u]; i+1; i = e[i].next) {
            int v = e[i].v, value1 = w[u], value2 = w[v];
            //下面是核心代码
            if (ans[v] < max(ans[u], value2 - value1)) {
                ans[v] = max(ans[u], value2 - value1);
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    return ;
}

int main() {
    scanf("%d%d", &n, &m);
    init();
    int i, x, y, z;
    for (i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    for (i = 1; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        if (z == 1) add(x, y);
        else {
            add(x, y);
            add(y, x);
        }
    }
    spfa(1);
    printf("%d", ans[n]);
    return 0;
}