HDU 1535 / POJ 1511 Invitation Cards：SPFA 双向最短路

题目大意

有向图 P 个站点（1 为中心 CCS），Q 条单向线路。每天志愿者从 CCS 出发到各站点，傍晚返回。求每日总往返最短路费用和。

解法：双向 SPFA

1. 原图跑 SPFA(1) → 得 dist1[v] = 1→v 最短路
2. 反图跑 SPFA(1) → 得 dist2[v] = v→1 最短路
3. 答案 = Σ(dist1[v] + dist2[v])

SPFA 模板（邻接表 + 队列）

struct Edge { int v, w; };
vector g[MAXN];
int dist[MAXN]; bool inq[MAXN];

void spfa(int s, int n) {
    fill(dist, dist+n+1, INF);
    fill(inq, inq+n+1, false);
    dist[s] = 0;
    queue q; q.push(s); inq[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        for (auto &e : g[u]) {
            if (dist[e.v] > dist[u] + e.w) {
                dist[e.v] = dist[u] + e.w;
                if (!inq[e.v]) { q.push(e.v); inq[e.v] = true; }
            }
        }
    }
}

主程序

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int P, Q; scanf("%d%d", &P, &Q);
        for (int i=1;i<=P;++i) g[i].clear();
        for (int i=0;i

POJ vs HDU 差异

POJ 数据更大，需 long long 存距离和
POJ 时间限制更严，建议用静态数组 + 手写队列优化常数


复杂度

SPFA 平均 O(kE)，k 为平均入队次数，实测极快
双向各跑一次，总 O(E)