仓库急送

知识点与目标

单源最短路径、堆优化 Dijkstra。前置：有向图邻接表、优先队列、复杂度与 long long。

解题思路

把配送站看成顶点，单向线路看成非负权有向边。维护 d[v] 表示已发现的从总部 s 到 v 的最短路线长度。初始化 d[s]=0，其余为 INF。小根堆保存（距离，顶点），每次取出最小距离；若取出的距离不等于当前 d[u]，跳过过期条目。遍历 u 的出边，用 d[u]+w 尝试更新 d[v]，成功后重新入堆。

正确性说明

非负边权保证：取出最小有效距离的顶点 u 时，若存在更短路线，沿该路线第一个尚未确定的顶点，在其前驱被处理时就应得到不大于这条路线长度的候选距离，与 u 的距离最小矛盾。因此有效出堆的距离即真实最短距离。每次松弛均对应一条实际路线，所有可达顶点均会沿路线获得候选距离；结束时 INF 恰好表示不可达。零权边不影响上述结论。

易错点

线路有方向；允许重边和零权边；普通 BFS 不能处理不同权值；第一次被松弛不代表已经确定最短路；必须跳过过期条目。源点不一定是1，不可达输出-1。距离使用 long long，INF=2^62，合法最短距离不超过 (n-1)×10^9。

复杂度

允许重复入堆，至多 O(m+1) 次入堆，时间 O(n+m log(m+2))，空间 O(n+m)。

难度依据

4·普及，geekpi-9-v2。需要完成有向带权图建模，根据10万顶点和20万条边选择高效算法，并处理过期堆项及64位距离；没有额外的多层状态扩展或算法组合。

C++17 参考代码

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <functional>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n,m,s; if(!(cin>>n>>m>>s)) return 0;
    vector<vector<pair<int,long long>>> g(n+1);
    for(int i=0,u,v;i<m;i++){long long w;cin>>u>>v>>w;g[u].push_back({v,w});}
    const long long INF=(1LL<<62);
    vector<long long> d(n+1,INF); d[s]=0;
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> pq;
    pq.push({0,s});
    while(!pq.empty()){
        auto cur=pq.top();pq.pop();long long du=cur.first;int u=cur.second;
        if(du!=d[u]) continue;
        for(auto e:g[u]) if(d[e.first]>du+e.second){d[e.first]=du+e.second;pq.push({d[e.first],e.first});}
    }
    for(int i=1;i<=n;i++){if(i>1)cout<<' ';cout<<(d[i]==INF?-1:d[i]);}cout<<'\n';
}