请教各位大佬，为什么我这道题总是WA，是那个细节没有注意到吗？
本帖最后由 zhangjinxuan 于 2022-11-20 19:43 编辑原题链接：
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;
int n, m, k, u, v, s, front, rear, step;
bool in_s;
bool a;
vector<Info> edges;
void bfs() {
memset(step, 255, sizeof(step));
rear = front = 1;
q = {1, 0};
step = 0;
while (rear + 1 != front) {
Info f = q;
//printf("%d %d : ", f.x, f.y);
if (f.x == n) {
if (step == -1) printf("%d", step);
else if (step == -1) printf("%d", step);
else printf("%d", min(step, step));
return;
}
for (Info i : edges) {
if (((f.y == 1 && i.y == 0) || (f.y == 0 && i.y == 1)) && step == -1) {
step = step + 1;
q[++rear] = {i.x, 0};
//printf("(OK)");
} else if (in_s && step == -1) {
step = step + 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.push_back({v, a});
edges.push_back({u, a});
}
for (int i = 1; i <= k; ++i) {
scanf("%d", &s);
in_s] = 1;
}
bfs();
return 0;
}
不知道是思路错了还是细节错了，希望大佬给予解答{:10_303:} @tommyyu @陈尚涵 @柿子饼同学 @xiaosi4081 你们会吗，希望解答，感谢！ 等我吃个饭先
不过我已经退役的说...
我是真的不理解为什么不用现成的 queue 柿子饼同学 发表于 2022-11-21 18:41
等我吃个饭先
不过我已经退役的说...
我是真的不理解为什么不用现成的 queue
我觉得效率《慢》，而且不灵活，不方便调试 zhangjinxuan 发表于 2022-11-21 19:16
我觉得效率《慢》，而且不灵活，不方便调试
好吧 ,我只能说 , 我不会做...
如果我能去参加特长生考试 , 我就会继续学的{:10_266:} 柿子饼同学 发表于 2022-11-21 20:02
好吧 ,我只能说 , 我不会做...
如果我能去参加特长生考试 , 我就会继续学的
啊，那算了，我问问老师 本帖最后由 xiaosi4081 于 2022-11-22 08:00 编辑
zhangjinxuan 发表于 2022-11-21 08:44
@tommyyu @陈尚涵 @柿子饼同学 @xiaosi4081 你们会吗，希望解答，感谢！
完了太难了
djkstra板子打的挺不错的{:10_256:}
不过....假设用djkstra的话你用不用优先队列啊 xiaosi4081 发表于 2022-11-22 07:49
完了太难了
djkstra板子打的挺不错的
AT第五题，是很难，估计我的上限也就第四题了{:10_266:}
有人吗？？？？ zhangjinxuan 发表于 2022-11-22 07:55
AT第五题，是很难，估计我的上限也就第四题了
优先队列可以试试 本帖最后由 zhangjinxuan 于 2022-11-22 08:20 编辑
xiaosi4081 发表于 2022-11-22 08:00
优先队列可以试试
优先队列？？是 priority_queue 吗？这不是堆的实现吗？？？怎么个做法？？ zhangjinxuan 发表于 2022-11-22 08:19
优先队列？？是 priority_queue 吗？这不是堆的实现吗？？？怎么个做法？？
就是把你那个队列搞成优先队列 xiaosi4081 发表于 2022-11-22 08:49
就是把你那个队列搞成优先队列
bfs的队列用优先队列？从来没见过! zhangjinxuan 发表于 2022-11-22 08:57
bfs的队列用优先队列？从来没见过!
不应该跑最短路吗 xiaosi4081 发表于 2022-11-22 09:05
不应该跑最短路吗
那好吧，我逝世 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, step;
bool in_s;
bool a;
vector<Info> edges;
void bfs() {
memset(step, 255, sizeof(step));
q.push({1, 0});
step = 0;
while (!q.empty()) {
Info f = q.top();
q.pop();
if (f.x == n) {
if (step == -1) printf("%d", step);
else if (step == -1) printf("%d", step);
else printf("%d", min(step, step));
return;
}
for (Info i : edges) {
//printf("(%d, %d), ", i.x, i.y);
if (((f.y == 1 && i.y == 0) || (f.y == 0 && i.y == 1)) && step == -1) {
step = step + 1;
q.push({i.x, 0});
//printf("(OK)");
} else if (in_s && step == -1) {
step = step + 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.push_back({v, a});
edges.push_back({u, a});
}
for (int i = 1; i <= k; ++i) {
scanf("%d", &s);
in_s] = 1;
}
bfs();
return 0;
} zhangjinxuan 发表于 2022-11-22 09:10
不对啊，你一个 struct 怎么优先？
用pair+priorty_queue xiaosi4081 发表于 2022-11-22 09:10
用pair+priorty_queue
好吧，逝世双关键字 xiaosi4081 发表于 2022-11-22 09:10
用pair+priorty_queue
我觉得就是某个细节错了，谁家的 BFS 用的是优先队列啊，我不信
页:
[1]