一、题目
1、原题链接
1488. 最短距离
2、题目描述
有 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、思路分析
思路来源：y总讲解视频
y总yyds
（1）将每个商店看做起点，在图中添加一个虚拟源点（起点），该点到其后面所有商店的距离均为0（有向边），则可以将从村庄走到商店的最短路径转化为从村庄走到源点（也就是从源点到村庄）的最短路径，两者等价。
（2）模拟上述过程，求从虚拟源点到村庄的最短路径，即为从村庄到商店的最短路径。
2、时间复杂度
时间复杂度为O(mlogn)（n表示点数，m表示边数）
3、代码详解
#include <iostream>
#include <queue>
#include <cstring>
#include <utility>
using namespace std;
typedef pair<int,int> PII;
const int N=100010,M=3*N; //N代表点数，M代表边数，因需要为每个起点添加一条由虚拟源点指向的边，所以开成点数3倍
int dist[N]; //存储每个点到虚拟源点的最短路径
int h[N],e[M],w[M],ne[M],idx; //h[]存储每个点第一条边的idx，e[]存储每条边的终点，ne[]存储每条边同起点的下一条边的idx，idx存储边的编号
bool st[N];
int n,m;
//邻接表中添加一条边
void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
//堆优化dijkstra求最短路
int dijkstra(){
memset(dist,0x3f,sizeof dist);
priority_queue<PII,vector<PII>,greater<PII>> heap;
dist[0]=0;
heap.push({0,0});
while(!heap.empty()){
PII t=heap.top();
heap.pop();
int ver=t.second;
if(st[ver]) continue;
st[ver]=true;
for(int i=h[ver];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[ver]+w[i]){
dist[j]=dist[ver]+w[i];
heap.push({dist[j],j});
}
}
}
if(dist[n]==0x3f3f3f3f) return -3;
else return dist[n];
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
int k;
cin>>k;
while(k--){
int x;
cin>>x;
add(0,x,0); //添加一个虚拟源点到每个商店距离为0的有向边
}
dijkstra();
int q;
cin>>q;
while(q--){
int y;
cin>>y;
cout<<dist[y]<<endl;
}
return 0;
}
三、知识风暴
Dijkstra算法
基本思想：将一个带权有向图中的顶点分成两组，一组是未确定最短路的，一组是已确定最短路的。每次将未确定最短路集合中的点，按照与源点的距离递增加入已确定最短路的集合中，同时每次往已确定最短路集合中加入一个点后，需要用这个点来更新其他点距离源点的距离。当所有点的最短路都已确定，算法结束。
