spaf判断有无负环
//不能只从1开始做一边spaf，因为不一定是“联通块”，可以对每个节点做一遍spaf，优化，构建虚拟节点
//检查负权环的：法1：到某点经过的边数多于（点数-1） 法2：某点被更新（点数-1）次，也就是入队n次
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
const int N=2001,M=10001;
int n,m;
vector<pii> adj[N];
int dis[N];
int st[N];
int cnt[N];
bool spaf(){
    for(int i=1;i<=n;i++) dis[i]=1e18;
    queue<int> que;
    que.push(0);
    st[0]=1;
    while(!que.empty()){
        auto x=que.front();
        que.pop();
        st[x]=0;
        for(auto [y,s]:adj[x]){
            if(dis[y]>dis[x]+s){
                cnt[y]=cnt[x]+1;
                if(cnt[y]>n) return true;
                dis[y]=dis[x]+s;
                if(!st[y]){
                    que.push(y);
                    st[y]=1;
                }
            }
        }
    }
    return false;
}
signed main(){
    cin>>n>>m;
    int a,b,c;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
    }
    for(int i=1;i<=n;i++){
        adj[0].push_back({i,0});
    }
    if(spaf()){
        cout<<"Yes\n";
    }else{
        cout<<"No\n";
    }
}

二分or最短路dp
注意：动态规划是有向无环图（有向会死循环，无切入），为什么这里面也可以运用：因为边权都是正的，保证收敛性；
粗浅的理解，分层dijk，spaf这些在状态上是无环，但是遍历上可能有环，负权环会破环这种结构

//这道题天生适合spaf，因为是边权，如果是dijk，得多存一个边权去贪心

spaf分层dp
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
const int N=1001,M=10001;
int n,m,k;
vector<pii> adj[N];
int dis[N][N];
int st[N][N];
void spaf(){
    for(int i=1;i<=n;i++) 
    for(int j=0;j<=k;j++)
    dis[i][j]=1e18;

    queue<pii> que;
    que.push({1,k});
    st[1][k]=1;
    dis[1][k]=0;

    while(!que.empty()){
        auto [x,kk]=que.front();
        que.pop();
        st[x][kk]=0;

        for(auto [y,s]:adj[x]){
            if(dis[y][kk]>max(dis[x][kk],s)){
                dis[y][kk]=max(dis[x][kk],s);
                if(!st[y][kk]){
                    que.push({y,kk});
                    st[y][kk]=1;
                }
            }


            if(kk>0&&dis[y][kk-1]>dis[x][kk]){
                dis[y][kk-1]=dis[x][kk];
                if(!st[y][kk-1]){
                    que.push({y,kk-1});
                    st[y][kk-1]=1;
            }
        }
        }
    }
}
signed main(){
    cin>>n>>m>>k;
    int a,b,c;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    spaf();
    int mmin=1e18;
    for(int i=0;i<=k;i++){
        mmin=min(dis[n][i],mmin);
    }
    if(mmin>=1e9){
        cout<<-1;
    }else
    cout<<mmin<<"\n";
}
//dijk分层
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 1001, M = 10001;
int n, m, k;
vector<pii> adj[N];
int dis[N][N];
bool vis[N][N];

void dijk() {
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= k; j++)
            dis[i][j] = 1e18;
    dis[1][0] = 0; 
    //存边权让贪心，其他存状态
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
    pq.push({0, {1, 0}});

    while (!pq.empty()) {
        auto current = pq.top();
        pq.pop();
        int current_max = current.first;
        int u = current.second.first;
        int j = current.second.second;

        if (vis[u][j]) continue;
        vis[u][j] = true;

        for (auto &edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;

            // 不使用免费次数，更新最大边权
            int new_max = max(current_max, w);
            if (new_max < dis[v][j]) {
                dis[v][j] = new_max;
                pq.push({new_max, {v, j}});
            }

            // 使用免费次数（如果还有剩余）
            if (j < k) {
                if (current_max < dis[v][j + 1]) {
                    dis[v][j + 1] = current_max;
                    pq.push({current_max, {v, j + 1}});
                }
            }
        }
    }
}

signed main() {
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }

    dijk();

    int mmin = 1e18;
    for (int i = 0; i <= k; i++)
        mmin = min(mmin, dis[n][i]);

    if (mmin == 1e18)
        cout << -1 << endl;
    else
        cout << mmin << endl;

    return 0;
}
//二分加01bfs
#include <bits/stdc++.h>
using namespace std;

const int N = 1001;
const int INF = 1e9 + 7;
vector<pair<int, int>> adj[N];
int dis[N]; // 当前需要花费的免费次数

// 检查能否在最多使用k次免费的情况下，让路径最大边权 <= mid
bool check(int n, int k, int mid) {
    fill(dis, dis + N, INF);
    deque<int> q;

    dis[1] = 0;
    q.push_back(1);

    while (!q.empty()) {
        int u = q.front();
        q.pop_front();

        for (auto [v, w] : adj[u]) {
            int cost = (w > mid) ? 1 : 0; // 超过mid的边需要消耗免费次数

            if (dis[v] > dis[u] + cost) {
                dis[v] = dis[u] + cost;
                // 0成本边插队首，1成本边插队尾，保证贪心
                cost ? q.push_back(v) : q.push_front(v);
            }
        }
    }
    return dis[n] <= k;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    // 二分找最小可行值
    int l = 0, r = 1e6 + 1, ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(n, k, mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    cout << (ans > 1e6 ? -1 : ans) << endl;
    return 0;
}

待补
题解：小优化和dijk拓扑

！！！所以要根据状态的变化来确定，观察状态不是单调性的

为何不用dijk：1单点多次调整，和不单调

//spaf联通性动态规划
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
const int N=100001,M=500001;
int n,m;
int a[N];
vector<int> adjz[N],adjf[N];
int dmin[N],dmax[N];
int st1[N],st2[N];

void spaf1(){
    for(int i=1;i<=n;i++) dmin[i]=1e18;
    dmin[1]=a[1];
    queue<int> que;
    que.push(1);
    st1[1]=1;
    while(!que.empty()){
        auto x=que.front();
        que.pop();
        st1[x]=0;
        for(auto son:adjz[x]){
            if(dmin[son]>min(dmin[x],a[son])){  
                dmin[son]=min(dmin[x],a[son]);  
                if(!st1[son]){
                    st1[son]=1;
                    que.push(son);
                }
            }
        }
    }
}

void spaf2(){
    for(int i=1;i<=n;i++) dmax[i]=-1e18;
    dmax[n]=a[n]; 
    queue<int> que;
    que.push(n);
    st2[n]=1;
    while(!que.empty()){
        auto x=que.front();
        que.pop();
        st2[x]=0;
        for(auto son:adjf[x]){
            if(dmax[son]<max(dmax[x],a[son])){
                dmax[son]=max(dmax[x],a[son]);
                if(!st2[son]){
                    st2[son]=1;
                    que.push(son);
                }
            }
        }
    }
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    int a,b,c;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        if(c==1){
            adjz[a].push_back(b);
            adjf[b].push_back(a);
        }else{
            adjz[a].push_back(b);  
            adjz[b].push_back(a);  
            adjf[b].push_back(a);  
            adjf[a].push_back(b);
        }
    }
    spaf1();
    spaf2();
    int mmax=0;
    for(int i=1;i<=n;i++){
        if(dmin[i]>=1e9 || dmax[i]<=-1e9) continue;
        mmax=max(mmax,dmax[i]-dmin[i]);
    }
    cout<<mmax;
}
//分层版本加sle优化
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, INF = 1e9;
int price[N], dis[N][3];  // dis[i][0/1/2]: 到达i时未购买/已购买/已卖出状态的最大收益
vector<int> adj[N];       // 邻接表存储原图
bool inq[N][3];           // 标记节点状态是否在队列中

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; ++i) cin >> price[i];
    while(m--) {
        int x,y,z;
        cin >> x >> y >> z;
        adj[x].push_back(y);
        if(z == 2) adj[y].push_back(x);
    }

    // 初始化状态
    for(int i=1; i<=n; ++i) 
        dis[i][0] = dis[i][1] = dis[i][2] = -INF;
    dis[1][0] = 0;

    deque<pair<int, int>> dq;
    dq.emplace_back(1, 0);
    inq[1][0] = true;

    while(!dq.empty()) {
        auto [u, s] = dq.front(); dq.pop_front();
        inq[u][s] = false;

        if(s == 0) { // 未购买状态
            // 1. 尝试购买
            if(dis[u][1] < dis[u][0] - price[u]) {
                dis[u][1] = dis[u][0] - price[u];
                if(!inq[u][1]) {
                    // SLF优化：优先处理较大值
                    if(!dq.empty() && dis[u][1] > dis[dq.front().first][dq.front().second]) 
                        dq.emplace_front(u, 1);
                    else 
                        dq.emplace_back(u, 1);
                    inq[u][1] = true;
                }
            }
            // 2. 传播未购买状态
            for(int v : adj[u]) {
                if(dis[v][0] < dis[u][0]) {
                    dis[v][0] = dis[u][0];
                    if(!inq[v][0]) {
                        if(!dq.empty() && dis[v][0] > dis[dq.front().first][dq.front().second])
                            dq.emplace_front(v, 0);
                        else
                            dq.emplace_back(v, 0);
                        inq[v][0] = true;
                    }
                }
            }
        } 
        else if(s == 1) { // 持有状态
            // 1. 尝试卖出
            if(dis[u][2] < dis[u][1] + price[u]) {
                dis[u][2] = dis[u][1] + price[u];
                if(!inq[u][2]) {
                    if(!dq.empty() && dis[u][2] > dis[dq.front().first][dq.front().second])
                        dq.emplace_front(u, 2);
                    else
                        dq.emplace_back(u, 2);
                    inq[u][2] = true;
                }
            }
            // 2. 传播持有状态
            for(int v : adj[u]) {
                if(dis[v][1] < dis[u][1]) {
                    dis[v][1] = dis[u][1];
                    if(!inq[v][1]) {
                        if(!dq.empty() && dis[v][1] > dis[dq.front().first][dq.front().second])
                            dq.emplace_front(v, 1);
                        else
                            dq.emplace_back(v, 1);
                        inq[v][1] = true;
                    }
                }
            }
        } 
        else { // 已卖出状态
            // 只能传播已卖出状态
            for(int v : adj[u]) {
                if(dis[v][2] < dis[u][2]) {
                    dis[v][2] = dis[u][2];
                    if(!inq[v][2]) {
                        if(!dq.empty() && dis[v][2] > dis[dq.front().first][dq.front().second])
                            dq.emplace_front(v, 2);
                        else
                            dq.emplace_back(v, 2);
                        inq[v][2] = true;
                    }
                }
            }
        }
    }

    int ans = max({dis[n][0], dis[n][1], dis[n][2]});
    cout << max(ans, 0) << "\n"; // 至少可以不交易
}

多起点怎么解决？设置虚拟起点

轮到只能用bfs和dijk版本的分层，这道题要求存在拓扑序
：边权为1时，SPFA和BFS就等价了，如果边权不一致时，是不能在找最短路的过程中记录最短路的条数的，因为SPFA本身不具有拓扑序，是一种迭代的思想；不能保证完全计算

上一题的升级版：记住分层dp，是层间的转化

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;

// 邻接表结构体
struct Edge {
    int to;     // 目标节点
    int weight; // 边权
};

vector<Edge> adj[N]; // 邻接表
int dis[N][2];       // dis[i][0]表示最短路，dis[i][1]表示次短路
int cnt[N][2];       // cnt[i][0]表示最短路数量，cnt[i][1]表示次短路数量
bool st[N][2];       // st[i][0]表示最短路是否已确定，st[i][1]表示次短路是否已确定

// 优先队列节点
struct Node {
    int index;      // 节点编号
    bool type;      // 路径类型：0表示最短路，1表示次短路
    int distance;   // 当前路径长度

    // 重载运算符，用于优先队列排序
    bool operator>(const Node& other) const {
        return distance > other.distance;
    }
};

void dijkstra(int start) {
    // 初始化
    memset(dis, 0x3f, sizeof(dis));
    memset(cnt, 0, sizeof(cnt));
    memset(st, 0, sizeof(st));

    priority_queue<Node, vector<Node>, greater<Node>> pq;

    // 起点初始化
    dis[start][0] = 0;
    cnt[start][0] = 1;
    pq.push({start, 0, 0});

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();

        int u = current.index;
        bool type = current.type;

        // 如果已经处理过，跳过
        if (st[u][type]) continue;
        st[u][type] = true;

        // 遍历所有邻接边
        for (const Edge& edge : adj[u]) {
            int v = edge.to;
            int w = edge.weight;

            // 计算新距离
            int new_dist = dis[u][type] + w;

            // 情况1：发现更短的最短路
            if (new_dist < dis[v][0]) {
                // 将原来的最短路降级为次短路
                dis[v][1] = dis[v][0];
                cnt[v][1] = cnt[v][0];
                pq.push({v, 1, dis[v][1]});

                // 更新最短路
                dis[v][0] = new_dist;
                cnt[v][0] = cnt[u][type];
                pq.push({v, 0, dis[v][0]});
            }
            // 情况2：发现相同长度的最短路
            else if (new_dist == dis[v][0]) {
                cnt[v][0] += cnt[u][type];
            }
            // 情况3：发现更短的次短路
            else if (new_dist < dis[v][1]) {
                dis[v][1] = new_dist;
                cnt[v][1] = cnt[u][type];
                pq.push({v, 1, dis[v][1]});
            }
            // 情况4：发现相同长度的次短路
            else if (new_dist == dis[v][1]) {
                cnt[v][1] += cnt[u][type];
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;

        // 清空邻接表
        for (int i = 1; i <= n; i++) {
            adj[i].clear();
        }

        // 读入边
        for (int i = 0; i < m; i++) {
            int a, b, l;
            cin >> a >> b >> l;
            adj[a].push_back({b, l});
        }

        int s, f;
        cin >> s >> f;

        dijkstra(s);

        // 输出结果：最短路数量 + (如果次短路长度=最短路长度+1，则加上次短路数量)
        int result = cnt[f][0];
        if (dis[f][1] == dis[f][0] + 1) {
            result += cnt[f][1];
        }
        cout << result << endl;
    }

    return 0;
}

类bfs水波四散求铺满时间==层数叠满（最长的路径）
见图方式：横坐标，线段型通路例如从a到b在c，等价于与建立两条单独的边ab和bc
费用转化路线距离，有点间的等价限制？，枚举限制区间

floy下的连通性，通过松弛操作，联通块内任一点距离都是《INF，两个点在不同连通块就是》INF，枚举连接点和ij各自最大的距离

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const double INF = 1e18;
const int N = 151;
double b[N][N];
int gg[N][N];
vector<pii> adj;

double dist(int a, int b, int c, int d) {
    return sqrt((a-c)*(a-c) + (b-d)*(b-d));
}

double max_dist[N];

signed main() {
    int n;
    cin >> n;
    adj.push_back({0, 0}); 
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        adj.push_back({x, y});
    }

    string s;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        s = '0' + s;  
        for (int j = 1; j <= n; j++) {
            gg[i][j] = s[j] - '0';
            if (!gg[i][j]) {
                b[i][j] = INF;
            } else {
                b[i][j] = dist(adj[i].first, adj[i].second, adj[j].first, adj[j].second);
            }
        }
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                     b[i][j] = min(b[i][j], b[i][k] + b[k][j]);
            }
        }
    }

     double ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (b[i][j] != INF) {
                max_dist[i] = max(max_dist[i], b[i][j]);
            }
        }
        ans = max(ans, max_dist[i]);
    }

    double result = 1e18;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (b[i][j] >= INF) {
                double d = dist(adj[i].first, adj[i].second, adj[j].first, adj[j].second);
                result = min(result, max_dist[i] + max_dist[j] + d);
            }
        }
    }

    cout << fixed << setprecision(6) << max(result,ans) << "\n";
    return 0;
}

foly的k为什么放外面，其实是三维dp优化，表示的是使用前k个点更新的最小距离

不理解严格次小生成树

krus算法用于处理边，发现此题有两种操作：点和边，那么可以建立一个超级原点连接所有的点，边权就是原来的点权
树有n-1个点，有多少个不用直接实时记录

计算生成的最小树，然后枚举爆力换一条边