题目描述

有 N 个村庄，编号 1 到 N。

村庄之间有 M 条无向道路，第 i 条道路连接村庄 ai 和村庄 bi，长度是 ci。

所有村庄都是连通的。

共有 K 个村庄有商店，第 j 个有商店的村庄编号是 xj。

然后给出 Q 个询问，第 k 个询问给出一个村庄的编号 yk，问该村庄距离最近的商店有多远？

输入格式
第一行包含两个整数 N,M。

接下来 M 行，每行包含三个整数 ai,bi,ci，表示第 i 条道路连接村庄 ai 和村庄 bi，长度是 ci。

再一行包含整数 K。

接下来 K 行，每行包含一个整数 xj，表示第 j 个有商店的村庄编号是 xj。

再一行包含整数 Q。

接下来 Q 行，每行包含一个整数 yk，表示询问编号为 yk 的村庄与其距离最近的商店之间的距离。

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

数据范围
2≤N≤105,
N−1≤M≤min(N(N−1)2,105),
1≤Q≤105,
1≤K≤N,
1≤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

算法1

C++ 代码

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 1e6+40;
const int inf = 0x3f3f3f3f3f;
struct egde{
    int to;
    int next;
    int dis;
}e[N << 1];
int head[N << 1],dis[N << 1],n,m,k,Q,idx;
bool vis[N << 1]={false};
inline void add(int u, int v, int d)
{
    idx++;
    e[idx].to = v;
    e[idx].dis = d;
    e[idx].next = head[u];
    head[u] = idx;
}
void spfa()
{
    queue<int>q;
    dis[0];
    q.push(0);
    vis[0] = true;
    while(q.size())
    {
        int x = q.front();
        q.pop();
        vis[x] = false;
        for(int i = head[x];i;i=e[i].next)
        {
            int y = e[i].to;
            if(dis[y] > dis[x] + e[i].dis)
            {
                dis[y] = dis[x] + e[i].dis;
                if(!vis[y])
                {
                    q.push(y);
                    vis[y] = true;
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n; i++){
        dis[i] = inf;
    }
    for(int i = 1;i <= m; i++){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        add(u,v,d);
        add(v,u,d);
    }
    scanf("%d", &k);
    while (k -- )
    {
        int v;
        scanf("%d", &v);             
        add(0, v, 0);
    }

    spfa();

    scanf("%d", &Q);
    while (Q -- )
    {
        int v;
        scanf("%d", &v);
        printf("%d\n", dis[v]);
    }

    return 0;
}