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

問題描述

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

建模

去掉耗油 > V 的邊，判斷剩餘圖中從 1 是否能到達所有點。即單源連通性問題。

SPFA 實現（實為 BFS）

#include 
#include 
using namespace std;
const int MAXV = 10005, MAXE = 100005, INF = 0x3f3f3f3f;
struct Edge { int to, w, next; } E[MAXE];
int head[MAXV], d[MAXV], 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