[已解决]请教各位大佬，为什么我这道题总是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


输入样例

1. 5 5 2
   
2. 1 3 0
   
3. 2 3 1
   
4. 5 4 1
   
5. 2 1 1
   
6. 1 4 0
   
7. 3 4

复制代码

输出样例

1. 5

复制代码

我的代码

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. struct Info {
   
5.         int x;
   
6.         bool y;
   
7. } q[501001];
   
8. 
   
9. int n, m, k, u, v, s[200001], front, rear, step[200001][2];
   
10. bool in_s[200001];
    
11. bool a;
    
12. vector<Info> edges[200001];
    
13. 
    
14. void bfs() {
    
15.         memset(step, 255, sizeof(step));
    
16.         rear = front = 1;
    
17.         q[rear] = {1, 0};
    
18.         step[1][0] = 0;
    
19.         while (rear + 1 != front) {
    
20.                 Info f = q[front++];
    
21.                 //printf("%d %d : ", f.x, f.y);
    
22.                 if (f.x == n) {
    
23.                         if (step[f.x][0] == -1) printf("%d", step[f.x][1]);
    
24.                         else if (step[f.x][1] == -1) printf("%d", step[f.x][0]);
    
25.                         else printf("%d", min(step[f.x][0], step[f.y][1]));
    
26.                         return;
    
27.                 }
    
28.                 for (Info i : edges[f.x]) {
    
29.                                 if (((f.y == 1 && i.y == 0) || (f.y == 0 && i.y == 1)) && step[i.x][0] == -1) {
    
30.                                         step[i.x][0] = step[f.x][f.y] + 1;
    
31.                                         q[++rear] = {i.x, 0};
    
32.                                         //printf("(OK)");
    
33.                                 } else if (in_s[f.x] && step[i.x][1] == -1) {
    
34.                                         step[i.x][1] = step[f.x][f.y] + 1;
    
35.                                         q[++rear] = {i.x, 1};
    
36.                                 }
    
37.                 }
    
38.         }
    
39.         printf("-1");
    
40. }
    
41. 
    
42. int main() {
    
43.         scanf("%d%d%d", &n, &m, &k);
    
44.         for (int i = 1; i <= m; ++i) {
    
45.                 scanf("%d%d%d", &u, &v, &a);
    
46.                 edges[u].push_back({v, a});
    
47.                 edges[v].push_back({u, a});
    
48.         }
    
49.         for (int i = 1; i <= k; ++i) {
    
50.                 scanf("%d", &s[i]);
    
51.                 in_s[s[i]] = 1;
    
52.         }
    
53.         bfs();
    
54.     return 0;
    
55. }

复制代码

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

最佳答案

月排行榜 / 总排行榜

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 怎么优先？

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. struct Info {
   
5.         int x;
   
6.         bool y;
   
7. };
   
8. priority_queue<Info> q;
   
9. 
   
10. int n, m, k, u, v, s[200001], step[200001][2];
    
11. bool in_s[200001];
    
12. bool a;
    
13. vector<Info> edges[200001];
    
14. 
    
15. void bfs() {
    
16.         memset(step, 255, sizeof(step));
    
17.         q.push({1, 0});
    
18.         step[1][0] = 0;
    
19.         while (!q.empty()) {
    
20.                 Info f = q.top();
    
21.                 q.pop();
    
22.                 if (f.x == n) {
    
23.                         if (step[f.x][0] == -1) printf("%d", step[f.x][1]);
    
24.                         else if (step[f.x][1] == -1) printf("%d", step[f.x][0]);
    
25.                         else printf("%d", min(step[f.x][0], step[f.y][1]));
    
26.                         return;
    
27.                 }
    
28.                 for (Info i : edges[f.x]) {
    
29.                         //printf("(%d, %d), ", i.x, i.y);
    
30.                                 if (((f.y == 1 && i.y == 0) || (f.y == 0 && i.y == 1)) && step[i.x][0] == -1) {
    
31.                                         step[i.x][0] = step[f.x][f.y] + 1;
    
32.                                         q.push({i.x, 0});
    
33.                                         //printf("(OK)");
    
34.                                 } else if (in_s[f.x] && step[i.x][1] == -1) {
    
35.                                         step[i.x][1] = step[f.x][f.y] + 1;
    
36.                                         q.push({i.x, 1});
    
37.                                         //printf("(ZOK");
    
38.                                 }
    
39.                 }
    
40.                 //puts("");
    
41.         }
    
42.         printf("-1");
    
43. }
    
44. 
    
45. int main() {
    
46.         scanf("%d%d%d", &n, &m, &k);
    
47.         for (int i = 1; i <= m; ++i) {
    
48.                 scanf("%d%d%d", &u, &v, &a);
    
49.                 edges[u].push_back({v, a});
    
50.                 edges[v].push_back({u, a});
    
51.         }
    
52.         for (int i = 1; i <= k; ++i) {
    
53.                 scanf("%d", &s[i]);
    
54.                 in_s[s[i]] = 1;
    
55.         }
    
56.         bfs();
    
57.     return 0;
    
58. }

复制代码

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 用的是优先队列啊，我不信