---

题目大意

给定一个有向图，$n$ 个点 $m$ 条边，边权为正整数。
再给定 $k$ 个特殊点，要求找出这 $k$ 个特殊点之间两两最短距离的最小值。

注意：是有向图，$a$ 到 $b$ 和 $b$ 到 $a$ 的路径长度可能不同，也可能不存在路径。

---

样例分析

样例1

6 7 3
1 5 3
2 3 5
1 4 3
5 3 2
4 6 5
4 3 7
5 6 4
1 3 6

特殊点：$1, 3, 6$

计算：

• $1 \to 3$：路径 $1\to 5\to 3$，长度 $3+2=5$
• $1 \to 6$：路径 $1\to 4\to 6$，长度 $3+5=8$（或 $1\to 5\to 6$ 长度 $3+4=7$）
• $3 \to 1$：无路径
• $3 \to 6$：无路径
• $6 \to 1$：无路径
• $6 \to 3$：无路径

最近点对是 $(1,3)$，距离 $5$。

---

思路分析

1. 暴力做法（不可行）

直接枚举 $k$ 个点的所有点对，对每个点对跑单源最短路。
复杂度：$O(k \cdot m\log n)$，当 $k$ 很大时不可行。

2. 多源最短路优化

我们并不需要所有点对，只需要找到最小值。可以利用这个性质进行优化。

关键观察：最近的特殊点对 $(u,v)$ 一定满足 $u$ 和 $v$ 在某个最短路树中相邻（在路径上相邻）。

---

标准解法：多源 Dijkstra

算法步骤

1. 建立一个超级源点 $S$，连接到所有 $k$ 个特殊点，边权为 $0$
2. 从 $S$ 开始跑 Dijkstra
3. 当扩展到一个特殊点 $u$ 时，记录它是从哪个特殊点 $v$ 扩展过来的
4. 如果 $u$ 和 $v$ 是不同的特殊点，那么 $(v,u)$ 就是一个候选的最近点对

原理：
在 Dijkstra 算法中，当我们第一次遇到一个特殊点 $u$ 时，它一定是离源点 $S$ 最近的特殊点之一。
如果 $u$ 是从另一个特殊点 $v$ 扩展过来的，那么 $v$ 到 $u$ 的路径就是当前已知的最短路径之一。

---

具体实现细节

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;

const ll INF = 2e18;

ll solve() {
    int n, m, k;
    cin >> n >> m >> k;
    
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
    }
    
    vector<int> special(k);
    for (int i = 0; i < k; i++) {
        cin >> special[i];
    }
    
    ll ans = INF;
    
    // 从超级源点S=0开始
    vector<ll> dist(n + 1, INF);
    vector<int> from(n + 1, -1);  // 记录是从哪个特殊点扩展来的
    
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    
    // 初始化：所有特殊点加入队列
    for (int i = 0; i < k; i++) {
        int u = special[i];
        dist[u] = 0;
        from[u] = u;  // 从自己扩展来
        pq.emplace(0, u);
    }
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d != dist[u]) continue;
        
        // 如果u是特殊点，且不是第一次被扩展（即从其他特殊点扩展来）
        if (from[u] != -1 && from[u] != u) {
            // 这里找到了一对特殊点 (from[u], u)，距离为d
            ans = min(ans, d);
        }
        
        for (auto [v, w] : g[u]) {
            ll nd = d + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                from[v] = from[u];  // 继承来源特殊点
                pq.emplace(nd, v);
            }
        }
    }
    
    return ans == INF ? -1 : ans;
}

---

算法正确性证明

设最近的特殊点对是 $(A,B)$，距离为 $d$。
在 Dijkstra 执行过程中，当扩展到 $B$ 时：

• 如果 $B$ 是从 $A$ 扩展过来的，那么我们会发现这对点，距离为 $d$
• 如果 $B$ 是从其他点 $C$ 扩展过来的，那么 $dist[C] + w(C,B) \le d$，且 $C$ 也是特殊点，这与 $(A,B)$ 是最近点对矛盾

因此算法一定能找到最近的特殊点对。

---

复杂度分析

• 时间复杂度：$O(m\log n)$，与普通 Dijkstra 相同
• 空间复杂度：$O(n + m)$

这比暴力 $O(k \cdot m\log n)$ 优化了很多。

---

注意事项

1. 有向图：路径是单向的，$A\to B$ 和 $B\to A$ 要分开考虑
2. 无穷大处理：如果所有特殊点对都不可达，需要特殊处理
3. 边权范围：$z \le 2\times 10^9$，要用 long long 存储距离

---

样例验证

样例2

7 7 4
5 3 10
6 2 7
1 2 6
5 4 2
4 3 4
1 7 3
7 2 4
1 2 5 3

特殊点：$1, 2, 5, 3$

计算发现：

• $1 \to 2$：路径 $1\to 7\to 2$，长度 $3+4=7$；或 $1\to 2$ 直接长度 $6$
• $5 \to 3$：路径 $5\to 4\to 3$，长度 $2+4=6$

最近距离是 $6$。

---

总结

本题的关键在于：

1. 识别出这是有向图多源最短路问题
2. 利用 Dijkstra 的性质，在扩展过程中直接检测最近点对
3. 通过超级源点技巧，将多源问题转化为单源问题

这种解法优雅地避免了暴力枚举，将复杂度从 $O(k\cdot m\log n)$ 降为 $O(m\log n)$，能够处理大规模数据。