#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#define N 114514
#define INF 0x7f7f7f7f

using namespace std;

struct edge{int v, w;};
int n, m;
int stdot, enddot;
vector<edge> e[N];
queue<int> que;
char maps[314][314];
int alpha[26][2];
int dist[N], vis[N];
int shifts[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool flag[26];
int dot(int x, int y){
	return x*m+y;
}

signed main(){
	memset(dist, 0x7f, sizeof(dist));
	memset(alpha, -1, sizeof(alpha));
	
	cin >> n >> m;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cin >> maps[i][j];
			if(maps[i][j]>='A' and maps[i][j]<='Z'){
				if(alpha[maps[i][j]-'A'][0] == -1)
					alpha[maps[i][j]-'A'][0] = dot(i, j);
				else
					alpha[maps[i][j]-'A'][1] = dot(i, j);
			}
			if(maps[i][j] == '@')
				stdot = dot(i, j);
			if(maps[i][j] == '=')
				enddot = dot(i, j);
		}
	}
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(maps[i][j] != '#'){
				for(int k=0; k<4; k++){
					if(maps[i+shifts[k][0]][j+shifts[k][1]] >= 'A' and
					   maps[i+shifts[k][0]][j+shifts[k][1]] <= 'Z' and
					   alpha[maps[i+shifts[k][0]][j+shifts[k][1]]-'A'][1] != -1){
					   	if(alpha[maps[i+shifts[k][0]][j+shifts[k][1]]-'A'][1] == dot(i+shifts[k][0], j+shifts[k][1]))
						   	e[dot(i, j)].push_back({alpha[maps[i+shifts[k][0]][j+shifts[k][1]]-'A'][0], 1});
						else
							e[dot(i, j)].push_back({alpha[maps[i+shifts[k][0]][j+shifts[k][1]]-'A'][1], 1});
					   }
					else if(maps[i+shifts[k][0]][j+shifts[k][1]] != '#'){
						e[dot(i, j)].push_back({dot(i+shifts[k][0], j+shifts[k][1]), 1});
						e[dot(i+shifts[k][0], j+shifts[k][1])].push_back({dot(i, j), 1});
					}
					
				}
			}
		}
	}
	
	que.push(stdot);
	dist[stdot] = 0; vis[stdot] = 1;
	
	while(que.size()){
		int u = que.front();
		que.pop(); vis[u] = 0;
		
		for(auto ed : e[u]){
			int v = ed.v, w = ed.w;
			if(dist[v] > dist[u] + w){
				dist[v] = dist[u] + w;
				if(!vis[v]) que.push(v), vis[v] = 1;
			}
		}
	}
	
	cout << dist[enddot];
}

提交记录

这是错误的代码，仅仅改了一处，它就A了.

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#define N 114514
#define INF 0x7f7f7f7f

using namespace std;

struct edge{int v, w;};
int n, m;
int stdot, enddot;
vector<edge> e[N];
queue<int> que;
char maps[314][314];
int alpha[26][2];
int dist[N], vis[N];
int shifts[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool flag[26];
int dot(int x, int y){
	return x*m+y;
}

signed main(){
	memset(dist, 0x7f, sizeof(dist));
	memset(alpha, -1, sizeof(alpha));
	
	cin >> n >> m;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cin >> maps[i][j];
			if(maps[i][j]>='A' and maps[i][j]<='Z'){
				if(alpha[maps[i][j]-'A'][0] == -1)
					alpha[maps[i][j]-'A'][0] = dot(i, j);
				else
					alpha[maps[i][j]-'A'][1] = dot(i, j);
			}
			if(maps[i][j] == '@')
				stdot = dot(i, j);
			if(maps[i][j] == '=')
				enddot = dot(i, j);
		}
	}
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(maps[i][j] != '#'){
				for(int k=0; k<4; k++){
					if(maps[i+shifts[k][0]][j+shifts[k][1]] >= 'A' and
					   maps[i+shifts[k][0]][j+shifts[k][1]] <= 'Z' and
					   alpha[maps[i+shifts[k][0]][j+shifts[k][1]]-'A'][1] != -1){
					   	if(alpha[maps[i+shifts[k][0]][j+shifts[k][1]]-'A'][1] == dot(i+shifts[k][0], j+shifts[k][1]))
						   	e[dot(i, j)].push_back({alpha[maps[i+shifts[k][0]][j+shifts[k][1]]-'A'][0], 1});
						else
							e[dot(i, j)].push_back({alpha[maps[i+shifts[k][0]][j+shifts[k][1]]-'A'][1], 1});
					   }
					else if(maps[i+shifts[k][0]][j+shifts[k][1]] != '#'){
						e[dot(i, j)].push_back({dot(i+shifts[k][0], j+shifts[k][1]), 1});  // 这里.
					}
					
				}
			}
		}
	}
	
	que.push(stdot);
	dist[stdot] = 0; vis[stdot] = 1;
	
	while(que.size()){
		int u = que.front();
		que.pop(); vis[u] = 0;
		
		for(auto ed : e[u]){
			int v = ed.v, w = ed.w;
			if(dist[v] > dist[u] + w){
				dist[v] = dist[u] + w;
				if(!vis[v]) que.push(v), vis[v] = 1;
			}
		}
	}
	
	cout << dist[enddot];
}

如果未修改这处代码，每两个能走的点会多出额外两条重边，这对重边如何影响答案？求助dalao.