最短路输出路径

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=1010;
int n;
int g[N][N];
PII pre[N][N];
PII q[N*N];
void bfs(int sx,int sy){
	int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
	memset(pre,-1,sizeof pre);
	int hh=0,tt=0;
	q[0]={sx,sy};
	while(hh<=tt){
		PII c=q[hh++];
		for(int i=0;i<4;i++){
			int cx=c.x+dx[i],cy=c.y+dy[i];
			if(g[cx][cy])continue;
			if(cx<0||cx>=n||cy<0||cy>=n)continue;
			if(pre[cx][cy].x!=-1)continue;
			q[++tt]={cx,cy};
			pre[cx][cy]={c.x,c.y};
		}
	}
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)cin>>g[i][j];
	bfs(n-1,n-1);
	PII end(0,0);
	while(true){
		printf("%d %d\n",end.x,end.y);
		if(end.x==n-1)break;
		end=pre[end.x][end.y];
	}
}

最短路输出路径

原文：https://www.cnblogs.com/codjjj/p/15213876.html