摘要
Title: 1488. 最短距离
Tag: dijkstra、最短路、超级源点
Memory Limit: 64 MB
Time Limit: 1000 ms

1488. 最短距离

题意

有 N个村庄，编号 1到 N
村庄之间有 M条无向道路，第 i条道路连接村庄 ai和村庄 bi，长度是 ci
所有村庄都是连通的
共有 K个村庄有商店，第 j个有商店的村庄编号是 xj
然后给出 Q个询问，第 k个询问给出一个村庄的编号 yk，问该村庄距离最近的商店有多远？
思路

下面都是等价式子

查询的点到商店的最短距离
等价于 所有的商店到查询的点的最短距离
（此时建立超级源点0，向所有商店连一条边权为0的有向边）
等价于 超级源点到查询的点的最短距离

而查询的点有Q个，而超级源点只有一个，所以dijkstra即可

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-03-04 16:16:41
* @FilePath: \Acwing\1488\1488.cpp
* @LastEditTime: 2023-03-04 16:44:53
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

int n, m, q, k;
vector<PII> g[N];
int dist[N], st[N];
int vis[N];

void dij(int s)
{
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, s});
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[s] = 0;
    while (SZ(q))
    {
        auto [_, u] = q.top();
        q.pop();
        if (st[u])
            continue;
        st[u] = 1;
        for (auto &[v, w] : g[u])
        {
            if (dist[u] + w <= dist[v])
            {
                dist[v] = dist[u] + w;
                q.push({dist[v], v});
            }
        }
    }
    return;
}

signed main()
{
    IOS;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    cin >> k;
    for (int i = 1; i <= k; ++i)
    {
        int x;
        cin >> x;
        // 新增超级源点，连向所有商店
        g[0].push_back({x, 0});
    }
    dij(0);
    cin >> q;
    while (q--)
    {
        int x;
        cin >> x;
        cout << dist[x] << '\n';
    }
    return 0;
}

1488. 最短距离

题意

思路

代码