AcWing
1488. 最短距离
堆优化dijkstra. 建立一个虚拟的源点，与各个商店的距离都为0，这样求与任意一个商店的最短距离就等价为求到虚拟源点的最短距离。以虚拟源点为起点做dijkstra，对每次查询，只需要输出dist[i]即可。
朴素的dijkstra的时间复杂度是$O(n^2)$，需要使用堆优化的dijkstra，其时间复杂度为$O(nlogn)$，本质上是维护一个小顶堆，有对数级别的取最小值时间。使用优先队列priority_queue来完成。
优先队列priority_queue默认是大顶堆，改成小顶堆需要定义priority_queue<type, vector<type>, greater<type>>. 对于pair<>，其大小取决于内部第一个元素(.first)，所以需要把距离放在first位(.first)，节点放在second位(.second)。可以参考：c++ priority_queue用法 入门必看 超详细.
#include <bits/stdc++.h>
using namespace std;
int n, m, k, q;
const int N = 100010, M = N * 3;
typedef pair<int, int> PII;
int h[N], e[M], w[M], ne[M], idx; // 邻接表表头索引，邻接表内的边，边权，邻接表指针，索引变量
int dist[N];
bool visited[N];
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dijk(){
priority_queue<PII, vector<PII>, greater<PII>> heap;
memset(dist, 0x3f, sizeof dist);
memset(visited, 0, sizeof visited);
heap.push({0, 0});
dist[0] = 0;
while(!heap.empty()){
auto temp = heap.top();
heap.pop();
int ver = temp.second;
if(visited[ver]) continue;
visited[ver] = 1;
for(int i = h[ver]; ~i; 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});
}
}
}
}
int main(){
memset(h, -1, sizeof h);
cin >> n >> m;
while(m--){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
cin >> k;
while(k--){
int a;
cin >> a;
add(0, a, 0);
}
dijk();
cin >> q;
while(q--){
int a;
cin >> a;
cout << dist[a] << endl;
}
return 0;
}