#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10, M = 3e5 + 10;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int n, m, k, p;
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void spfa()
{
memset(dist, 0x3f, sizeof dist);
queue<int> q;
dist[0] = 0;
st[0] = true;
q.push(0);
while (q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; ~i; i = ne[i]) // ~i 相当于 i != -1
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h); //清空邻接表表头
while (m -- ) //按照yls的代码,后面连续scanf三次m即可,但我发现过不了,得换三个不同的变量
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c); //读入边和权值
add(a, b, c); //连接两条有向边,得无向边
add(b, a, c);
}
scanf("%d", &k);
while (k -- )
{
int v;
scanf("%d", &v); //有商店的村子,距离商店的距离为0
add(0, v, 0);
}
spfa();
scanf("%d", &p);
while (p -- )
{
int v;
scanf("%d", &v);
printf("%d\n", dist[v]);
}
return 0;
}
M的最大值为什么是3e5 + 10?不应该是5*1e9嘛
你好,关于这个问题,其实M取不到5e9,由题目数据范围知当N取最大即N=1e5时,有 1e5 - 1 < M < min(5e9, 1e5) = 1e5。之所以M的最大值为什么是3e5 + 10,首先N最大是1e5,M为无向边应该有2e5条,又因为每个点要连接到一个超级原点,故再加1e5条,一共3e5条边。
明白了,谢谢