// Dijkstra 算法（优先队列）— O((V+E) log V)
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;   // {距离, 节点}
typedef long long ll;

const ll INF = 1e18;          // 使用 long long 避免 int 溢出！
const int MAXN = 100005;

// 邻接表：adj[u] = {权重, v} 列表
vector<pii> adj[MAXN];

vector<ll> dijkstra(int src, int n) {
    vector<ll> dist(n + 1, INF);   // dist[i] = 到节点 i 的最短距离
    dist[src] = 0;

    // 最小堆：{距离, 节点}
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();  // 取距离最小的节点

        // 关键：若已找到到 u 的更好路径则跳过（过期条目）
        if (d > dist[u]) continue;

        // 松弛 u 的所有邻居
        for (auto [w, v] : adj[u]) {
            ll newDist = dist[u] + w;
            if (newDist < dist[v]) {
                dist[v] = newDist;          // 更新距离
                pq.push({newDist, v});       // 将更新后的条目加入队列
            }
        }
    }
    return dist;
}

// Bellman-Ford 算法 — O(V * E)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef tuple<int, int, int> Edge;  // {起点, 终点, 权重}

const ll INF = 1e18;

// 返回最短距离数组，若检测到负环则返回空数组
vector<ll> bellmanFord(int src, int n, vector<Edge>& edges) {
    vector<ll> dist(n + 1, INF);
    dist[src] = 0;

    for (int iter = 0; iter < n - 1; iter++) {
        bool updated = false;
        for (auto& [u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;  // 提前收敛
    }

    // 第 V 次检查：检测从源点可达的负环
    for (auto& [u, v, w] : edges) {
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            return {};  // 存在负环
        }
    }

    return dist;
}

// Floyd-Warshall 全对最短路径 — O(V^3)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 1e18;
const int MAXV = 505;

ll dist[MAXV][MAXV];

void floydWarshall(int n) {
    // 初始化：dist[i][i]=0, 有边设为边权, 无边设为 INF
    // ...（读入时已完成）

    // ⚠️ 关键：k 必须是最外层循环！
    for (int k = 1; k <= n; k++) {         // 中转站
        for (int i = 1; i <= n; i++) {     // 起点
            for (int j = 1; j <= n; j++) { // 终点
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    // 若 dist[i][i] < 0，则节点 i 在负环上
}

// SPFA（Bellman-Ford + 队列优化）
vector<ll> spfa(int src, int n) {
    vector<ll> dist(n + 1, INF);
    vector<bool> inQueue(n + 1, false);
    vector<int> cnt(n + 1, 0);   // cnt[v] = v 进入队列的次数

    queue<int> q;
    dist[src] = 0;
    q.push(src);
    inQueue[src] = true;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        inQueue[u] = false;

        for (auto [w, v] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;

                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    cnt[v]++;

                    // 负环检测：若节点进入队列 >= n 次
                    if (cnt[v] >= n) return {};  // 负环！
                }
            }
        }
    }
    return dist;
}

// 判断全图负环（包含不可达部分）
// 建立超级源点 0，向所有节点连 0 权边，从 0 跑 Bellman-Ford
bool hasNegativeCycle(int n) {
    // 原图节点 1..n，超级源点 0
    vector<ll> dist(n + 1, 0);  // 全部初始化为 0（等价于超级源点到所有节点距离为 0）
    vector<bool> inQueue(n + 1, true);
    vector<int> cnt(n + 1, 0);
    queue<int> q;

    // 所有节点入队（超级源点效果）
    for (int i = 1; i <= n; i++) q.push(i);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        inQueue[u] = false;

        for (auto [w, v] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!inQueue[v]) {
                    q.push(v); inQueue[v] = true;
                    if (++cnt[v] >= n) return true;  // 负环！
                }
            }
        }
    }
    return false;
}

// Johnson 全源最短路 — O(NM log M)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

int n, m;
// adj[u] = {v, w}，edges 存所有边用于 Bellman-Ford
vector<pair<int,ll>> adj[505];
struct Edge { int u, v; ll w; };
vector<Edge> edges;

vector<ll> bellman_ford(int s) {
    vector<ll> dist(n + 1, INF);
    dist[s] = 0;
    for (int i = 0; i < n; i++) {
        for (auto [u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }
    return dist;
}

vector<ll> dijkstra(int s, int n) {
    vector<ll> dist(n + 1, INF);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    dist[s] = 0; pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

// 返回 dist[i][j] = i 到 j 的真实最短路
// 若 i 到 j 不可达返回 INF
vector<vector<ll>> johnson() {
    // 超级源点 n+1 向所有节点连 0 权边
    for (int i = 1; i <= n; i++)
        edges.push_back({n + 1, i, 0});

    // Bellman-Ford 求势函数 h[]
    vector<ll> h = bellman_ford(n + 1);

    // 重新标注边权（保证非负）
    for (auto& e : edges) {
        if (e.u != n + 1)  // 不处理超级源点的虚拟边
            e.w += h[e.u] - h[e.v];
    }
    // 同步更新邻接表
    for (int u = 1; u <= n; u++)
        for (auto& [v, w] : adj[u])
            w += h[u] - h[v];

    // N 次 Dijkstra
    vector<vector<ll>> ans(n + 1, vector<ll>(n + 1, INF));
    for (int s = 1; s <= n; s++) {
        auto d = dijkstra(s, n);
        for (int t = 1; t <= n; t++) {
            if (d[t] != INF)
                ans[s][t] = d[t] - h[s] + h[t];  // 还原真实距离
        }
    }
    return ans;
}

// Dijkstra 带路径输出
vector<int> dijkstra_with_path(int src, int dst, int n) {
    vector<ll> dist(n + 1, INF);
    vector<int> pre(n + 1, -1);  // pre[v] = v 的前驱
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;

    dist[src] = 0; pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pre[v] = u;          // 记录前驱
                pq.push({dist[v], v});
            }
        }
    }

    // 根据 pre[] 还原路径（逆序）
    vector<int> path;
    for (int v = dst; v != -1; v = pre[v])
        path.push_back(v);
    reverse(path.begin(), path.end());

    // 检查路径是否从 src 出发
    if (path.empty() || path[0] != src) return {};  // 不可达
    return path;  // src → ... → dst
}

// 0-1 BFS — O(V + E)，处理 {0,1} 权重边
vector<int> bfs01(int src, int n) {
    vector<int> dist(n + 1, INT_MAX);
    deque<int> dq;

    dist[src] = 0;
    dq.push_front(src);

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

        for (auto [w, v] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);   // 0 权重：加到前面
                else        dq.push_back(v);    // 1 权重：加到后面
            }
        }
    }
    return dist;
}

// 网格 Dijkstra — 找从 (0,0) 到 (R-1,C-1) 的最短路径
// 每个格子有进入代价
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef tuple<ll,int,int> tli;

const ll INF = 1e18;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

ll dijkstraGrid(vector<vector<int>>& grid) {
    int R = grid.size(), C = grid[0].size();
    vector<vector<ll>> dist(R, vector<ll>(C, INF));
    priority_queue<tli, vector<tli>, greater<tli>> pq;

    dist[0][0] = grid[0][0];
    pq.push({grid[0][0], 0, 0});

    while (!pq.empty()) {
        auto [d, r, c] = pq.top(); pq.pop();
        if (d > dist[r][c]) continue;

        for (int k = 0; k < 4; k++) {
            int nr = r + dx[k], nc = c + dy[k];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;

            ll newDist = dist[r][c] + grid[nr][nc];
            if (newDist < dist[nr][nc]) {
                dist[nr][nc] = newDist;
                pq.push({newDist, nr, nc});
            }
        }
    }
    return dist[R-1][C-1];
}

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

vector<int> bfs(int start, const vector<vector<int>>& adj) {
    int n = (int)adj.size() - 1;
    vector<int> dist(n + 1, INF);
    queue<int> q;
    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == INF) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

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

    // USACO 官方文件 I/O 可按需打开：
    // freopen("piggyback.in", "r", stdin);
    // freopen("piggyback.out", "w", stdout);

    long long bCost, eCost, togetherCost;
    int n, m;
    cin >> bCost >> eCost >> togetherCost >> n >> m;

    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<int> d1 = bfs(1, adj);
    vector<int> d2 = bfs(2, adj);
    vector<int> dn = bfs(n, adj);

    long long answer = LLONG_MAX;
    for (int meet = 1; meet <= n; meet++) {
        if (d1[meet] == INF || d2[meet] == INF || dn[meet] == INF) continue;
        long long cost = bCost * d1[meet] + eCost * d2[meet] + togetherCost * dn[meet];
        answer = min(answer, cost);
    }

    cout << answer << "\n";
    return 0;
}

复杂度： 三次 BFS，总时间 O(N+M)，空间 O(N+M)。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = (ll)4e18;

struct Edge {
    int to;
    int w;
};

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

    // USACO 官方文件 I/O 可按需打开：
    // freopen("shortcut.in", "r", stdin);
    // freopen("shortcut.out", "w", stdout);

    int n, m;
    ll t;
    cin >> n >> m >> t;

    vector<ll> cows(n + 1);
    for (int i = 1; i <= n; i++) cin >> cows[i];

    vector<vector<Edge>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }

    vector<ll> dist(n + 1, INF);
    vector<int> parent(n + 1, 0);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;

    dist[1] = 0;
    parent[1] = 0;
    pq.push({0, 1});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) continue;

        for (const Edge &e : adj[u]) {
            int v = e.to;
            ll nd = d + e.w;
            if (nd < dist[v] || (nd == dist[v] && u < parent[v])) {
                dist[v] = nd;
                parent[v] = u;
                pq.push({nd, v});
            }
        }
    }

    vector<vector<int>> tree(n + 1);
    for (int v = 2; v <= n; v++) {
        tree[parent[v]].push_back(v);
    }

    vector<ll> subtreeCows = cows;
    vector<int> order;
    order.reserve(n);
    stack<int> st;
    st.push(1);
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        order.push_back(u);
        for (int v : tree[u]) st.push(v);
    }

    for (int i = (int)order.size() - 1; i >= 0; i--) {
        int u = order[i];
        for (int v : tree[u]) {
            subtreeCows[u] += subtreeCows[v];
        }
    }

    ll answer = 0;
    for (int u = 1; u <= n; u++) {
        answer = max(answer, (dist[u] - t) * subtreeCows[u]);
    }

    cout << answer << "\n";
    return 0;
}

复杂度： Dijkstra O((N+M) log N)，建树和统计 O(N)，空间 O(N+M)。

从节点 1 做标准 Dijkstra。距离用 long long——最大路径 = N × 最大权重 = 10^5 × 10^9 = 10^14，int 会溢出。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int,int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<ll> dist(n + 1, LLONG_MAX);
    priority_queue<pli, vector<pli>, greater<pli>> pq;

    dist[1] = 0;
    pq.push({0, 1});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;

        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    cout << (dist[n] == LLONG_MAX ? -1 : dist[n]) << "\n";
    return 0;
}
// 时间：O((N + M) log N)，空间：O(N + M)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int R, C;
    cin >> R >> C;

    vector<string> grid(R);
    for (auto& row : grid) cin >> row;

    vector<vector<int>> dist(R, vector<int>(C, -1));
    queue<pair<int,int>> q;

    if (grid[0][0] != '#') {
        dist[0][0] = 0;
        q.push({0, 0});
    }

    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr >= 0 && nr < R && nc >= 0 && nc < C
                && grid[nr][nc] != '#' && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }

    cout << dist[R-1][C-1] << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<tuple<int,int,ll>> edges(m);
    for (auto& [u, v, w] : edges) cin >> u >> v >> w;

    const ll INF = 1e18;
    vector<ll> dist(n + 1, INF);
    dist[1] = 0;

    // Bellman-Ford：V-1 遍
    for (int iter = 0; iter < n - 1; iter++) {
        for (auto [u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // 第 V 遍：检测负环
    vector<bool> inNegCycle(n + 1, false);
    for (int iter = 0; iter < n; iter++) {
        for (auto [u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                inNegCycle[v] = true;
            }
            if (inNegCycle[u]) inNegCycle[v] = true;
        }
    }

    if (dist[n] == INF) cout << "UNREACHABLE\n";
    else if (inNegCycle[n]) cout << "NEGATIVE CYCLE\n";
    else cout << dist[n] << "\n";

    return 0;
}

多源 BFS：将所有 K 座感染城市以时间 0 加入队列。然后正常运行 BFS。这等价于添加一个虚拟「超级源点」通过 0 代价边连接到所有 K 座城市。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> dist(n + 1, -1);
    queue<int> q;

    // 将所有 K 个僵尸源以时间 0 压入
    for (int i = 0; i < k; i++) {
        int z; cin >> z;
        dist[z] = 0;
        q.push(z);
    }

    // 从所有源同时做标准 BFS
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    for (int u = 1; u <= n; u++) {
        cout << dist[u];
        if (u < n) cout << " ";
    }
    cout << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    const ll INF = 1e18;
    vector<vector<ll>> dist(n + 1, vector<ll>(n + 1, INF));

    for (int i = 1; i <= n; i++) dist[i][i] = 0;

    for (int i = 0; i < m; i++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w);
        dist[v][u] = min(dist[v][u], w);
    }

    // Floyd-Warshall：O(N³)
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    int q;
    cin >> q;
    while (q--) {
        int u, v; ll D;
        cin >> u >> v >> D;
        cout << (dist[u][v] <= D ? "YES" : "NO") << "\n";
    }

    return 0;
}
// 时间：O(N³ + Q)，空间：O(N²)

修改版 Dijkstra： 不是最小化总代价，而是最大化瓶颈。dist[v] = 到 v 的任意路径的最大最小边权。用最大堆。松弛：dist[v] = max(dist[v], min(dist[u], weight(u,v)))。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<vector<pii>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    // 修改版 Dijkstra：最大化瓶颈
    vector<int> dist(n + 1, 0);
    priority_queue<pii> pq;  // 最大堆：{瓶颈, 节点}

    dist[1] = INT_MAX;
    pq.push({INT_MAX, 1});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d < dist[u]) continue;

        for (auto [v, w] : adj[u]) {
            int newBottleneck = min(dist[u], w);  // ← 关键：取路径上的最小值
            if (newBottleneck > dist[v]) {
                dist[v] = newBottleneck;
                pq.push({dist[v], v});
            }
        }
    }

    cout << dist[n] << "\n";
    return 0;
}
// 时间：O((N + M) log N)，空间：O(N + M)