1因此如果把距离改成可能是0或者1的时候，BFS就可能不会再求出最短距离了，比如当前有一个离当前点距离是1的点待入队列，后续还有一个距离为0的点待入队列，这是完全可能的，但是因为距离是1的会先入队列，距离是0的点会后入队列，从而就破坏了BFS的正确性基于的事实：后入队列的点的离起点的距离一定比先入队列的点离起点的距离远(这里是单调不减)。但是我们可以这样：把队列换成双端队列deque，新的点入队列时，让距离为0的点插入队头，让距离为1的点插入队尾。

版权声明：本文转载「魔术师的徒弟」的原创文章。
原文链接：https://blog.csdn.net/CS_COPy/article/details/125052319
**例子

**
E - Crystal Switches
题目：
https://atcoder.jp/contests/abc277/tasks/abc277_e

上代码：
package com.hgs.atcoder.abc.contest277.e;

/**

• @author youtsuha
• @version 1.0
• Create by 2022/11/12 19:58
• /

import java.util.;
import java.io.;
public class Main {
static FastScanner cin;
static PrintWriter cout;
static int [][] dp;
private static void init()throws IOException {
cin = new FastScanner(System.in);
cout = new PrintWriter(System.out);
}

private static void close(){
    cout.close();
}
static int n, m, k;
static class node{
    int a, b, c;
    //[]
    public node(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
}
static List<node> e[];
static int ans = (int) 1e9;
static int inf = (int) 1e9;
static boolean isSwitch[];

// static boolean dfs(int x, int fa, int rot, int dep){
//
// }
private static void sol()throws IOException {
n = cin.nextInt(); m = cin.nextInt(); k = cin.nextInt();
dp = new int[n][2];
// Arrays.fill(dp[0],inf);
// Arrays.fill(dp[1],inf);
for(int j = 0; j < 2; j ++ ) {
for(int i = 0; i < n; i ++ ){
//cout.print(dp[i][j] + " ");
dp[i][j] = inf;
}
// cout.println("");
}
e = new ArrayList[n];
isSwitch = new boolean[n];
for(int i = 0; i < n; i ++ ) {
e[i] = new ArrayList<>();
}
for(int i = 0; i < m; i ++ ) {
int a = cin.nextInt(), b = cin.nextInt(), c = cin.nextInt();
a--; b--;
e[a].add(new node(b,c,0));
e[b].add(new node(a,c,0));
}
for(int i = 0; i < k; i ++ ) {
int x = cin.nextInt(); x--;
isSwitch[x] = true;
}
// dfs(0,-1,0, 0);
PriorityQueue que = new PriorityQueue<>((a,b)->a.c - b.c);
dp[0][0] = 0;
que.add(new node(0,0,0));
while(!que.isEmpty()){
int x = que.peek().a, d = que.peek().c, rot= que.peek().b;
que.poll();
if(dp[x][rot] > d) {
continue;
}
for(int i = 0; i < e[x].size(); i ++ ) {
int v = e[x].get(i).a, p = e[x].get(i).b;
int nxt = (p + rot) % 2;
if(nxt % 2 == 1){
if(dp[v][rot] > d + 1){
dp[v][rot] = Math.min(dp[v][rot], d + 1);
que.add(new node(v,rot,d+1));
}
}else if(isSwitch[x]){
nxt = (rot + 1) % 2;
if(dp[v][nxt] > d + 1){
dp[v][nxt] = Math.min(dp[v][nxt], d + 1);
que.add(new node(v,nxt, d + 1));
}
}
}
}
int ans = inf;
if(dp[n-1][0] != inf) {
ans = Math.min(ans, dp[n-1][0]);
}if(dp[n-1][1] != inf) {
ans = Math.min(ans, dp[n-1][1]);
}
if(ans == inf) {
cout.println(-1);
}else {
cout.println(ans);
}
}
public static void main(String[] args) throws IOException {
init();
sol();
close();
}
}
class FastScanner {
BufferedReader br;
StringTokenizer st = new StringTokenizer("");

public FastScanner(InputStream s) {
    br = new BufferedReader(new InputStreamReader(s));
}

public FastScanner(String s) throws FileNotFoundException {
    br = new BufferedReader(new FileReader(new File(s)));
}

public String next() throws IOException {
    while (!st.hasMoreTokens()){
        try {
            st = new StringTokenizer(br.readLine());
        } catch (IOException e) { e.printStackTrace(); }
    }
    return st.nextToken();
}

public int nextInt() throws IOException {
    return Integer.parseInt(next());
}

public long nextLong() throws IOException {
    return Long.parseLong(next());
}

public double nextDouble() throws IOException {
    return Double.parseDouble(next());
}

}

****此代码转载
scau_sleep（今天写bug了吗？的博客