acwing1488. 最短距离（超级源点 spfa）

有 NN 个村庄，编号 11 到 NN。
村庄之间有 MM 条无向道路，第 ii 条道路连接村庄 aiai 和村庄 bibi，长度是 cici。
所有村庄都是连通的。
共有 KK 个村庄有商店，第 jj 个有商店的村庄编号是 xjxj。
然后给出 QQ 个询问，第 kk 个询问给出一个村庄的编号 ykyk，问该村庄距离最近的商店有多远？

输入格式

第一行包含两个整数 N,MN,M。
接下来 MM 行，每行包含三个整数 ai,bi,ciai,bi,ci，表示第 ii 条道路连接村庄 aiai 和村庄 bibi，长度是 cici。
再一行包含整数 KK。
接下来 KK 行，每行包含一个整数 xjxj，表示第 jj 个有商店的村庄编号是 xjxj。
再一行包含整数 QQ。
接下来 QQ 行，每行包含一个整数 ykyk，表示询问编号为 ykyk 的村庄与其距离最近的商店之间的距离。

输出格式

对于每个询问，输出该询问的结果。

数据范围

2≤N≤1052≤N≤105,
N−1≤M≤min(N(N−1)2,105)N−1≤M≤min(N(N−1)2,105),
1≤Q≤1051≤Q≤105,
1≤K≤N1≤K≤N,
1≤ci≤100001≤ci≤10000

输入样例：

7 7 1 2 5 1 4 3 2 3 2 2 5 1 3 6 7 5 6 8 6 7 6 3 7 5 4 7 1 2 3 4 5 6 7

输出样例：

3 1 3 0 0 6 0

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 3 * N;
int h[N], e[M], ne[M], w[M], idx;
int dist[N];
bool st[N];
int q[N]; //队列
int n, m;
void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
void spfa() {
    memset(dist, 0x3f, sizeof dist);
    int hh = 0, tt = 1;
    dist[0] = 0;
    st[0] = true;   //加入到队列
    while (hh != tt) {
        int t = q[hh ++];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    q[tt ++] = j;
                    st[j] = true;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
}
int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);   //无向边
        add(b, a, c);
    }
    cin >> m;
    //超级源点到商店村庄的距离设置为0
    for (int i = 1; i <= m; ++i) {
        int a;
        cin >> a;
        add(0, a, 0);
    }
    spfa();
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        int a;
        cin >> a;
        cout << dist[a] << endl;
    }
    return 0;
}