最优贸易 题解

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, d[maxn*3], inq[maxn*3];
vector<pair<int, int>> G[maxn*3];
#define t(x,i) (x+i*n)  // t(x,i) 表示第i层的x
// 建立x->y边的函数, 不用加 make_pair是 C++11特性
#define add(x, y) G[t(x,0)].push_back({t(y,0), 0}), G[t(x,1)].push_back({t(y,1),0}), G[t(x,2)].push_back({t(y,2),0})
void spfa(int s) {
    for(int i = 1;i <= n*3;i++) d[i] = INT_MIN; // 这里n*3别漏了, INT_MIN 是C++内置最小值常量
    d[s] = 0; 
    queue<int> Q; inq[s] = true; Q.push(s);
    while(!Q.empty()) {
        int x = Q.front(); Q.pop(); inq[x] = false;
        for(auto [v, len] : G[x])  // C++17 特性, 等价于 int v = G[x][i].first, len = G[x][i].second;
            if(d[v] < d[x] + len) {
                d[v] = d[x] + len;
                if(!inq[v]) { Q.push(v); inq[v] = true; }
            } 
    }
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); // 加速cin, cout
    cin >> n >> m;
    for(int i = 1, v;i <= n; ++i) {
        cin >> v;
        G[t(i,0)].push_back({t(i,1), -v});
        G[t(i,1)].push_back({t(i,2), v});
    }
    for(int i = 1,x,y,z;i <= m; ++i) {
        cin >> x >> y >> z; add(x, y);
        if(z == 2) add(y, x);
    }
    spfa(t(1,0));
    cout << d[t(n,2)] << endl;
    return 0;
}

欢迎加入团队