题目描述
问题分析 :
本题的问题是 : 在多个源点下求最短路(建立超级源点 ) 因为边权为1 可以直接考虑使用bfs来做
多源bfs可以参考提高课 https://www.acwing.com/problem/content/175/
重点分析 :
储存坐标图距离的dist数组
标志坐标图能否通过的g数组
以及队列PII
建立超级源点 (并不需要真实的建立 因为虚拟源点第一层扩展就将所有的源点加入队列 可以直接加入队列)
注意 :
开long long 是因为 2000 * 1000 * n方会爆int
多源bfs
n方
C++ 代码
// 边权为1源点不唯一 考虑多源bfs(直接将源点加入到队列当中) bfs 建图
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1010;
int dist[N][N];
int n, m, k, d;
queue<PII> q;
bool g[N][N];
struct C{
int x, y, w;
}w[N * N];
void bfs()
{
int dx[4] = {-1,0,1,0}, dy[4] = {0,-1,0,1};
while (q.size())
{
auto t = q.front();
q.pop();
for (int i = 0; i < 4; i ++)
{
int x = t.x + dx[i] , y = t.y + dy[i];
if (x < 1 || x > n || y < 1 || y > n || !g[x][y] ) continue;
if (dist[x][y] > dist[t.x][t.y] + 1)
{
dist[x][y] = dist[t.x][t.y] + 1;
q.push({x, y});
}
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&k,&d);
memset(dist, 0x3f, sizeof dist);
memset(g, 1, sizeof g);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
dist[a][b] = 0;
q.push({a, b}); // 放入源点
}
for (int i = 1; i <= k; i ++)
{
scanf("%d%d%d",&w[i].x, &w[i].y, &w[i].w);
}
while (d --)
{
int a, b;
scanf("%d%d", &a, &b);
g[a][b] = false; // 注意 : g本身的初始值就是false 如果设置为false 需要对g初始化
}
bfs();
LL res = 0;
for (int i = 1; i <= k; i ++)
{
res += w[i].w * dist[w[i].x][w[i].y];
}
cout << res << endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla