51nod 1706 最短路 + 思维

首先考虑到 会有边重合， 我们思考 如果有边重合 那一定会出现一个起始点 起始点 就是 重合的那个点 那么只需要 将到达点设为 三点的终点 就没有边重合了 51nod的数据较大 需要用deque 优化 bfs

#include<iostream>
#include<queue>
#include<cstring>
#define x first
#define y second

using namespace std;

typedef long long ll;

const int N = 1100;
typedef pair<int,int> PII;
int xx[4] = {
    0,1,0,-1};
int yy[4] = {
    1,0,-1,0};
char a[N][N];int dist1[N][N],dist2[N][N],dist3[N][N],flag[N][N];
int n,m;
void bfs(int dist[][N],int x){
    
    memset(flag,0,sizeof flag);
    deque<PII>q;
    for(int i = 1; i <= n; i++){
    
        for(int j = 1; j <= m; j++){
    
            if(a[i][j] - '0' == x) q.push_back({
    i,j}),dist[i][j] = 0;
        }
    }

    while(q.size()){
    
        PII p = q.front();
        q.pop_front();
        for(int i = 0; i < 4; i++){
    
            int x = p.x,y = p.y;
            int dx = x + xx[i],dy = y + yy[i];
            if(dx <= 0 || dx > n || dy <= 0 || dy > m || a[dx][dy] == '#') continue;
            if(a[x][y] == '.'){
    
                if(dist[x + xx[i]][y + yy[i]] > dist[x][y] + (a[x][y]=='.')){
    
                    dist[x + xx[i]][y + yy[i]] = dist[x][y] + (a[x][y]=='.');
                    q.push_back({
    dx,dy});
                }
            }else{
    
                if(dist[x + xx[i]][y + yy[i]] > dist[x][y] + (a[x][y]=='.')){
    
                    dist[x + xx[i]][y + yy[i]] = dist[x][y] + (a[x][y]=='.');
                    q.push_front({
    dx,dy});
                }
            }
        }
    }
}

int main(){
    
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
    
        scanf("%s",a[i] + 1);
    }

    memset(dist1,0x3f,sizeof dist1);
    memset(dist2,0x3f,sizeof dist2);
    memset(dist3,0x3f,sizeof dist3);

    bfs(dist1,1);
    bfs(dist2,2);
    bfs(dist3,3);


    ll sum = 0x3f3f3f3f3f3f3f3f;
    for(int i = 1; i <= n; i++){
    
        for(int j = 1; j <= m; j++){
    
            sum = min (sum,1ll * dist1[i][j] + dist2[i][j] + dist3[i][j] + (a[i][j] == '.'));
        }
    }

    if(sum > 1e9) cout << -1 << endl;
    else cout << sum  << endl;




    return 0;
}