堆优化版迪杰斯特拉算法

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef pair<int, int> PII;

int n, m, k, Q;
vector<int> dist;
vector<vector<PII>> adj;
vector<bool> st;

void dijsktra()
{
    priority_queue<PII, vector<PII>, greater<PII>> q;
    dist[0] = 0;
    q.push({ 0, 0 });

    while (q.size())
    {
        auto t = q.top();
        q.pop();
        int ver = t.second, d = t.first;
        if (st[ver]) continue;
        st[ver] = true;

        for (auto iter = adj[ver].begin(); iter != adj[ver].end(); iter++)
        {
            int j = iter->second;
            if (dist[j] > dist[ver] + iter->first)
            {
                dist[j] = dist[ver] + iter->first;
                q.push({ dist[j], j });
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    adj = vector<vector<PII>>(n + 1);
    dist = vector<int>(n + 1, 1e9);
    st = vector<bool>(n + 1, false);
    for (int i = 1; i <= m; i++)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        adj[a].push_back({ w, b });
        adj[b].push_back({ w, a });
    }

    cin >> k;
    for (int i = 1; i <= k; i++)
    {
        int a;
        scanf("%d", &a);
        adj[0].push_back({ 0, a });
    }

    dijsktra();

    cin >> Q;
    while (Q--)
    {
        int a;
        cin >> a;
        cout << dist[a] << endl;
    }
    return 0;
}