HLJ OJ 1214 Around the World：SPFA 判斷圖連通性（油箱容量限制）

問題描述

N 城市 (1 為起點)，M 條雙向路，每條路耗油 c。油箱容量 V，只能在城市加滿油。問能否從 1 出發走遍所有城市（可重複經過）。

建模與算法

只保留耗油 ≤ V 的邊，判斷從 1 出發能否到達所有點（即圖連通）。用 SPFA/BFS/DFS 求單源最短路或直接遍歷均可。

代碼實現 (SPFA)

#include 
#include 
using namespace std;
const int MAXN = 1000000+10, INF = 0x3f3f3f3f;
struct Edge { int to, w, next; } E[MAXN];
int head[MAXN], d[MAXN], V, M, C, ecnt;

void addEdge(int u, int v, int w) {
    E[ecnt] = {v, w, head[u]}; head[u] = ecnt++;
}

bool spfa(int s) {
    queue q; memset(d, 0x3f, sizeof(d));
    d[s] = 0; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; ~i; i = E[i].next) {
            int v = E[i].to;
            if (E[i].w <= C && d[v] > d[u] + E[i].w) {
                d[v] = d[u] + E[i].w;
                q.push(v);
            }
        }
    }
    for (int i = 1; i <= V; ++i) if (d[i] == INF) return false;
    return true;
}

int main() {
    while (scanf("%d%d%d", &V, &M, &C) == 3) {
        memset(head, -1, sizeof(head)); ecnt = 0;
        for (int i=0, a,b,c; i