A（双向奔赴）

(第一遍只跑了一遍spfa，错了)
关键点：“拉近距离”的不一定是小明，也可能是小红，
题目中没有给出具体的源点汇点，所以在做spfa的时候，
分别以1和n为源点各做一遍，取min

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1010, M = 10010;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N];
bool st[N];
void add(int a, int b, int c) 
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}
bool spfa(int x) 
{
    memset(dist, 0x3f, sizeof(dist));
    memset(st, false, sizeof(st));
    memset(cnt, 0, sizeof(cnt));
    dist[x] = 0;
    st[x] = true;
    queue <int> q;
    q.push(x);
    while (!q.empty()) 
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i!=-1; i = ne[i]) 
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) 
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) 
                    return true;
                if (!st[j]) 
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}
int main() 
{
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    while (m--) 
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, -c);
    }
    if (spfa(1)) 
    {
        puts("Forever love");
        return 0;
    }
    int ans = dist[n];
    if (spfa(n)) 
    {
        puts("Forever love");
        return 0;
    }
    cout << min(ans, dist[1]) << endl;
    return 0;
}

B（已解决）（新：超级源点||超级汇点 ）

给定n个城市的货物买卖价格， 然后给定n-1条道路，每条路有不同的路费， 求出从某两个城市买卖一次的最大利润。
利润 = 卖价 - （买价 + 路费）
1.如果一条边连接（u，v），路费为cost ，城市买卖价格用P( )表示那么他的边权就表达为(P(v) - P(u) - cost).
2.我们可以假设有一个起点。他连接着所有的点，边权为0。
3.那么如果从这个点出发的话， 就等于是把所有的城市都尝试作为买入城市
4.然后只要做一次允许有副权的SPFA最短路算法就能算出正确答案了。

考虑用最短路求法进行求解。
加一个超级源点和超级汇点，跑一遍最短路，
就可以了，但是我们求的是最长路。
所以把边取反求最短路就ok了，开始用dijstra跑崩了，
忘记了dij不能处理有负权边的图，所以跑了一遍spfa就过了。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, maxx = 0x3f3f3f3f;
int e[N * 2], ne[N * 2], w[N * 2], h[N], idx;
int dist[N];
bool st[N * 2];
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
void chushi()
{
    memset(st, false, sizeof st);
    memset(dist, -0x3f3f3f3f, sizeof dist);
    memset(h, -1, sizeof h);
    idx=0；
}
void spfa()
{
    queue<int>q;
    st[0] = true;
    dist[0] = 0;
    q.push(0);
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        st[t] = false;//防止负环
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
}
int main()
{
    int n, t;
    cin >> t;
    while (t--)
    {
        chushi();
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            int x;
            cin >> x;
            add(0, i, -x);//从超级源点0点取，边权的意思是买书的价格
            add(i, n + 1, x);//超级汇点(n+1)
        }
        for (int i = 1; i < n; i++)
        {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, -c);//双向边
            add(b, a, -c);
        }
        spfa();
        cout << dist[n + 1] << endl;
    }
    return 0;
}

C

判断是否存在负权环，存在返回yes

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int e[N], ne[N], idx, w[N],h[N],dist[N];
bool st[N];
int n, m, k,cnt[N];
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c,h[a]=idx++;
}
bool spfa()
{
    memset(st, false, sizeof st);
    memset(cnt, 0, sizeof cnt);
    memset(dist, 0, sizeof dist);
    queue<int>q;
    for (int i = 1; i <= n; i++)
    {
        q.push(i);
        st[i] = true;
    }
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n)return true;
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return false;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        idx = 0;
        memset(h, -1, sizeof h);
        cin >> n >> m >> k;
        for (int i = 1; i <= m; i++)
        {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c);
            add(b, a, c);
        }
        while (k--)
        {
            int a, c, b;
            cin >> a >> b >> c;
            add(a, b, -c);
        }
        if (spfa())
            puts("YES");
        else 
            puts("NO");
    }
    return 0;
}