[已解决]请教各位大佬，为什么我这道题总是WA，是那个细节没有注意到吗？

zhangjinxuan

原题链接：
https://atcoder.jp/contests/abc277/tasks/abc277_e

原题翻译：
来源于：https://www.luogu.com.cn/problem/AT_abc277_e

题面
给定一张 n 个点 m 条边的无向图，每条边有一个权值 w (0 <= w <= 1)， w = 0 表示无法通过，反之表示可通过

其中，有 k 个点上面有按钮，按下按钮，全部路的边权取反，即：w = 0 变成 1，w = 1 变成 0

你现在位于 1 号点，每次，你可以做两件事：
1. 移动到相邻的一个点上，前提是边可以通行;
2. 按按钮，前提是所在的点上有按钮


输入格式
第一行一个整数 n, m, k

接下来 m 行，每行三个数 u, v, w, 表示一条链接 u 与 v 的边，权值为 w

最后一行 k 个数，表示按钮的位置


输出格式
一个整数，表示最少移动步数，若无法到达，输出 -1


输入样例

5 5 2
1 3 0
2 3 1
5 4 1
2 1 1
1 4 0
3 4

输出样例

5

我的代码

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

struct Info {
        int x;
        bool y;
} q[501001];

int n, m, k, u, v, s[200001], front, rear, step[200001][2];
bool in_s[200001];
bool a;
vector<Info> edges[200001];

void bfs() {
        memset(step, 255, sizeof(step));
        rear = front = 1;
        q[rear] = {1, 0};
        step[1][0] = 0;
        while (rear + 1 != front) {
                Info f = q[front++];
                //printf("%d %d : ", f.x, f.y);
                if (f.x == n) {
                        if (step[f.x][0] == -1) printf("%d", step[f.x][1]);
                        else if (step[f.x][1] == -1) printf("%d", step[f.x][0]);
                        else printf("%d", min(step[f.x][0], step[f.y][1]));
                        return;
                }
                for (Info i : edges[f.x]) {
                                if (((f.y == 1 && i.y == 0) || (f.y == 0 && i.y == 1)) && step[i.x][0] == -1) {
                                        step[i.x][0] = step[f.x][f.y] + 1;
                                        q[++rear] = {i.x, 0};
                                        //printf("(OK)");
                                } else if (in_s[f.x] && step[i.x][1] == -1) {
                                        step[i.x][1] = step[f.x][f.y] + 1;
                                        q[++rear] = {i.x, 1};
                                }
                }
        }
        printf("-1");
}

int main() {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= m; ++i) {
                scanf("%d%d%d", &u, &v, &a);
                edges[u].push_back({v, a});
                edges[v].push_back({u, a});
        }
        for (int i = 1; i <= k; ++i) {
                scanf("%d", &s[i]);
                in_s[s[i]] = 1;
        }
        bfs();
    return 0;
}

不知道是思路错了还是细节错了，希望大佬给予解答

最佳答案

月排行榜 / 总排行榜

xiaosi4081

2022-11-22 09:10:34

zhangjinxuan 发表于 2022-11-22 09:10
不对啊，你一个 struct 怎么优先？

用pair+priorty_queue

跳转到最佳答案楼层

zhangjinxuan

@tommyyu @陈尚涵 @柿子饼同学 @xiaosi4081 你们会吗，希望解答，感谢！

柿子饼同学

等我吃个饭先
不过我已经退役的说...
我是真的不理解为什么不用现成的 queue

zhangjinxuan

柿子饼同学 发表于 2022-11-21 18:41
等我吃个饭先
不过我已经退役的说...
我是真的不理解为什么不用现成的 queue

我觉得效率《慢》，而且不灵活，不方便调试

柿子饼同学

zhangjinxuan 发表于 2022-11-21 19:16
我觉得效率《慢》，而且不灵活，不方便调试

好吧 ,  我只能说 , 我不会做...
如果我能去参加特长生考试 , 我就会继续学的

zhangjinxuan

柿子饼同学 发表于 2022-11-21 20:02
好吧 ,  我只能说 , 我不会做...
如果我能去参加特长生考试 , 我就会继续学的

啊，那算了，我问问老师

xiaosi4081

zhangjinxuan 发表于 2022-11-21 08:44
@tommyyu @陈尚涵 @柿子饼同学 @xiaosi4081 你们会吗，希望解答，感谢！

完了太难了

djkstra板子打的挺不错的

不过....假设用djkstra的话你用不用优先队列啊

zhangjinxuan

xiaosi4081 发表于 2022-11-22 07:49
完了太难了

djkstra板子打的挺不错的

AT第五题，是很难，估计我的上限也就第四题了

zhangjinxuan

有人吗？？？？

xiaosi4081

zhangjinxuan 发表于 2022-11-22 07:55
AT第五题，是很难，估计我的上限也就第四题了

优先队列可以试试

zhangjinxuan

xiaosi4081 发表于 2022-11-22 08:00
优先队列可以试试

优先队列？？是 priority_queue 吗？这不是堆的实现吗？？？怎么个做法？？

xiaosi4081

zhangjinxuan 发表于 2022-11-22 08:19
优先队列？？是 priority_queue 吗？这不是堆的实现吗？？？怎么个做法？？

就是把你那个队列搞成优先队列

zhangjinxuan

xiaosi4081 发表于 2022-11-22 08:49
就是把你那个队列搞成优先队列

bfs的队列用优先队列？从来没见过!

xiaosi4081

zhangjinxuan 发表于 2022-11-22 08:57
bfs的队列用优先队列？从来没见过!

不应该跑最短路吗

zhangjinxuan

xiaosi4081 发表于 2022-11-22 09:05
不应该跑最短路吗

那好吧，我逝世

zhangjinxuan

xiaosi4081 发表于 2022-11-22 09:05
不应该跑最短路吗

不对啊，你一个 struct 怎么优先？

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

struct Info {
        int x;
        bool y;
};
priority_queue<Info> q;

int n, m, k, u, v, s[200001], step[200001][2];
bool in_s[200001];
bool a;
vector<Info> edges[200001];

void bfs() {
        memset(step, 255, sizeof(step));
        q.push({1, 0});
        step[1][0] = 0;
        while (!q.empty()) {
                Info f = q.top();
                q.pop();
                if (f.x == n) {
                        if (step[f.x][0] == -1) printf("%d", step[f.x][1]);
                        else if (step[f.x][1] == -1) printf("%d", step[f.x][0]);
                        else printf("%d", min(step[f.x][0], step[f.y][1]));
                        return;
                }
                for (Info i : edges[f.x]) {
                        //printf("(%d, %d), ", i.x, i.y);
                                if (((f.y == 1 && i.y == 0) || (f.y == 0 && i.y == 1)) && step[i.x][0] == -1) {
                                        step[i.x][0] = step[f.x][f.y] + 1;
                                        q.push({i.x, 0});
                                        //printf("(OK)");
                                } else if (in_s[f.x] && step[i.x][1] == -1) {
                                        step[i.x][1] = step[f.x][f.y] + 1;
                                        q.push({i.x, 1});
                                        //printf("(ZOK");
                                }
                }
                //puts("");
        }
        printf("-1");
}

int main() {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= m; ++i) {
                scanf("%d%d%d", &u, &v, &a);
                edges[u].push_back({v, a});
                edges[v].push_back({u, a});
        }
        for (int i = 1; i <= k; ++i) {
                scanf("%d", &s[i]);
                in_s[s[i]] = 1;
        }
        bfs();
    return 0;
}

xiaosi4081

zhangjinxuan 发表于 2022-11-22 09:10
不对啊，你一个 struct 怎么优先？

用pair+priorty_queue

zhangjinxuan

xiaosi4081 发表于 2022-11-22 09:10
用pair+priorty_queue

好吧，逝世双关键字

zhangjinxuan

xiaosi4081 发表于 2022-11-22 09:10
用pair+priorty_queue

我觉得就是某个细节错了，谁家的 BFS 用的是优先队列啊，我不信