循环dp、spfa、松弛操作

题意：

分析：

其实，我标签里的所谓循环dp其实也就是类似分层图。不过是另一种角度看待问题而已。
我认为对于状态相互转移的图论问题应该适用。

首先，让我们回顾一下Bellman-Ford算法。
Bellman-Ford在试图解决最短路问题时总结了一个状态转移公式：
d[i] = min(d[k] + cost[k,i] k为i的相邻节点) d[i] 为节点i到节点1的最短距离

我们很容易就能发现如果所给的图不是一个DAG的话，那么这个dp公式是会陷入死循环的！
假设i和j构成一个环i需要j推出，j需要i推出。。。。。。

那么，Bellman-Ford是如何解决这个问题的呢？
松弛操作！

通过松弛操作，我么们成功破解了循环dp问题！！前提是没有负环

那么对于这题，我们该如何做呢？
给出状态方程：
dp[i][j] i节点在j状态下距离s的最短路
dp[i][0] 指到i节点已经买了
dp[i][1] 指到了i节点已经卖了

买的操作加cost[i]，卖的操作减cost[i]

那么给出状态转移公式:
dp[i][0] = min（min(dp[k][0] k为其邻节点)，cost[i]）
dp[i][1] = min(min(dp[k][1] k为其邻节点)，dp[i][0] - cost[i])

这就是一个循环dp，我们可以采用松弛操作，利用队列优化(spfa算法)因为有负边

但是，这题在进行状态转移有特殊的地方
我们设置dp[i][1] = dp[i][0] = inf作为默认
又dp[s][0] = cost[s]作为初始状态，然后由此状态进行更新。
dp[k][0] 更新dp[k][1],dp[i][0]
dp[k][1] 更新dp[i][1]
但是在dp[k][0] 更新dp[i][0]的过程中要考虑cost[i]的，这点万分注意！
可能说的不大好理解，可以看看我下面的代码。
或许循环dp的说法有点抽象，这题用分层图是很好解的，可以看看其他的题解。有一篇写的非常好

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> pii;
const int max_n = 1e5 + 100;
const int max_m = 5e5 + 100;
const int inf = 2e9;
int n;int m;
struct edge { int to, next; };
int cost[max_n];
int head[max_n];
edge E[max_m * 4];
int cnt;
int d[max_n][2];
bool used[max_n][2];

void addedge(int from,int to) {
    E[cnt].to = to;
    E[cnt].next = head[from];
    head[from] = cnt++;
}

int spfa(int s) {
    queue<pii> que;
    for (int i = 0;i <= n;i++) {
        used[i][1] = used[i][0] = 0;
        d[i][1] = d[i][0] = inf;
    }d[s][0] = cost[s];que.push({ s,0 });
    while (!que.empty()) {
        pii p = que.front();que.pop();
        int pos = p.first;int state = p.second;
        used[pos][state] = false;
        if (state == 1) {
            for (int i = head[pos];i;i = E[i].next) {
                if (d[E[i].to][1] > d[pos][1] && !used[E[i].to][1]) {
                    used[E[i].to][1] = true;
                    que.push({ E[i].to,1 });
                }d[E[i].to][1] = min(d[E[i].to][1], d[pos][1]);
            }
        }
        else if (state == 0) {
            if (d[pos][1] > d[pos][0] - cost[pos] && !used[pos][1]) {
                used[pos][1] = true;
                que.push({ pos,1 });
            }d[pos][1] = min(d[pos][1], d[pos][0] - cost[pos]);
            for (int i = head[pos];i;i = E[i].next) {
                int cmp = min(d[pos][0], cost[E[i].to]);
                if (d[E[i].to][0] > cmp && !used[E[i].to][0]) {
                    used[E[i].to][0] = true;
                    que.push({ E[i].to,0 });
                }d[E[i].to][0] = min(d[E[i].to][0], cmp);
            }
        }
    }
    return d[n][1];
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1;i <= n;i++)cin >> cost[i];
    for (int i = 1;i <= m;i++) {
        int type; int u, v;
        cin >> u >> v >> type;
        addedge(u, v);
        if (type == 2)addedge(v, u);
    }
    cout << -spfa(1) << endl;
}