有这样一个情景，对于很多源点，求得离他最近的目标的最短路径，称为多源最短路。这时可以创建一个虚拟源点，以边权为0连接所有的源点，这样就把多源最短路转化为了单源最短路
AcWing 173. 矩阵距离
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int n, m;
queue<pair<int, int>> q;
char a[1010][1010];
bool st[1010][1010];
int dis[1010][1010];
int bx[4] = {1,-1,0,0};
int by[4] = {0,0,1,-1};
void bfs()
{
while(!q.empty())
{
auto t = q.front();
int nowx = t.first, nowy = t.second;
q.pop();
for(int i = 0; i < 4; i ++ )
{
int nx = nowx + bx[i], ny = nowy + by[i];
if(nx < 1 || ny < 1 || nx > n || ny > m )continue;
if(st[nx][ny])continue;
q.push({nx, ny});
st[nx][ny] = true;
dis[nx][ny] = dis[nowx][nowy] + 1;
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ )
{
cin >> a[i][j];
if(a[i][j] == '1')
{
q.push({i,j});
st[i][j] = true;
}
}
bfs();
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ )
{
printf("%d ", dis[i][j]);
if(j == m)printf("\n");
}
}
