rt 原题 SCU4444 神奇

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 233;
vector <int> z[N];
int dis[N];
bool inque[N];
const int INF = 1e9;

signed main() {
    int n, m, a, b;
    while (scanf ("%lld%lld%lld%lld", &n, &m, &a, &b) == 4) {
        for (int i = 1; i <= n; i ++)
            z[i].clear();
        bool flag = false;
        while (m --) {
            int a, b;
            scanf ("%lld%lld", &a, &b);
            z[a].push_back(b);
            z[b].push_back(a);
            if (a == 1 && b == n || a == n && b == 1)
                flag = true;
        }
        if (flag) {
            memset (dis, 0, sizeof dis);
            dis[n] = INF;
            set <int> se1, se2;
            for (int i = 2; i <= n; i ++)
                se1.insert(i);
            queue <int> que;
            que.push(1);
            dis[1] = 0;
            while (que.size()) {
                int u = que.front();
                que.pop();
                for (auto &v : z[u])
                    if (se1.count(v)) {
                        se1.erase(v);
                        se2.insert(v);
                    }
                for (auto &v : se1) {
                    que.push(v);
                    dis[v] = dis[u] + b;
                }
                se1.swap(se2);
                se2.clear();
            }
            // for (int i = 1; i <= n; i ++)
            //     cout << dis[i] << ' ';
            // cout << '\n';
            printf ("%lld\n", min(a, dis[n]));
        } else {
            queue <int> que;
            for (int i = 0; i <= n; i ++)
                dis[i] = INF;
            // memset (inque, false, sizeof inque);
            que.push(1);
            dis[1] = 0;
            inque[1] = true;
            while (que.size()) {
                int u = que.front();
                que.pop();
                inque[1] = false;
                for (auto &v : z[u])
                    if (dis[v] > dis[u] + a) {
                        dis[v] = dis[u] + a;
                        if (!inque[v]) {
                            inque[v] = true;
                            que.push(v);
                        }
                    }
            }
            printf ("%lld\n", min(dis[n], b));
        }
    }
    return 0;
}

---

按说 inque 不用清空，可是 WA 了

然后清空了 inque

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 233;
vector <int> z[N];
int dis[N];
bool inque[N];
const int INF = 1e9;

signed main() {
    int n, m, a, b;
    while (scanf ("%lld%lld%lld%lld", &n, &m, &a, &b) == 4) {
        for (int i = 1; i <= n; i ++)
            z[i].clear();
        bool flag = false;
        while (m --) {
            int a, b;
            scanf ("%lld%lld", &a, &b);
            z[a].push_back(b);
            z[b].push_back(a);
            if (a == 1 && b == n || a == n && b == 1)
                flag = true;
        }
        if (flag) {
            memset (dis, 0, sizeof dis);
            dis[n] = INF;
            set <int> se1, se2;
            for (int i = 2; i <= n; i ++)
                se1.insert(i);
            queue <int> que;
            que.push(1);
            dis[1] = 0;
            while (que.size()) {
                int u = que.front();
                que.pop();
                for (auto &v : z[u])
                    if (se1.count(v)) {
                        se1.erase(v);
                        se2.insert(v);
                    }
                for (auto &v : se1) {
                    que.push(v);
                    dis[v] = dis[u] + b;
                }
                se1.swap(se2);
                se2.clear();
            }
            // for (int i = 1; i <= n; i ++)
            //     cout << dis[i] << ' ';
            // cout << '\n';
            printf ("%lld\n", min(a, dis[n]));
        } else {
            queue <int> que;
            for (int i = 0; i <= n; i ++)
                dis[i] = INF;
            memset (inque, false, sizeof inque);
            que.push(1);
            dis[1] = 0;
            inque[1] = true;
            while (que.size()) {
                int u = que.front();
                que.pop();
                inque[1] = false;
                for (auto &v : z[u])
                    if (dis[v] > dis[u] + a) {
                        dis[v] = dis[u] + a;
                        if (!inque[v]) {
                            inque[v] = true;
                            que.push(v);
                        }
                    }
            }
            printf ("%lld\n", min(dis[n], b));
        }
    }
    return 0;
}

就过了

但是

我spfa61行把inque[u]=false写成了inque[1]=false

为什么第二种能过 第一种WA了