T3-1 单源最短路径1

题意理解

给定 $n$ 个点 $m$ 条边的有向图，可能有重边，求从点 $s$ 出发到所有点的最短路径长度。不可达输出 $-1$。

---

思路分析

堆优化 Dijkstra

数据范围 $n \leq 10^6$，$m \leq 2 \times 10^6$，需要使用堆优化的 Dijkstra 算法。

算法流程：

1. 初始化所有点距离为无穷大，起点距离为 $0$
2. 用优先队列（小根堆）维护待处理的点
3. 每次取出距离最小的点 $u$，用它更新所有邻接点的距离
4. 已确定最短路的点不再处理

注意事项：

• 边权最大 $10^9$，路径长度可能超过 int，需用 long long
• 有重边不影响 Dijkstra 的正确性
• 不可达的点距离保持无穷大，输出 $-1$

复杂度： $O((n+m) \log n)$

---

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;          // 最大点数
const long long INF = 1e18;        // 无穷大

int n, m, s;                       // 点数、边数、起点
int head[MAXN], cnt;               // 邻接表头指针、边计数器

struct Edge {                      // 边结构体
    int to, nxt;                   // 终点、下一条边
    long long w;                   // 边权
} e[MAXN * 2];                     // 边数组

void addEdge(int u, int v, long long w) {  // 添加一条从u到v权值为w的边
    e[++cnt] = {v, head[u], w};    // 新边存入数组
    head[u] = cnt;                 // 更新头指针
}

long long dis[MAXN];               // dis[i]表示起点到i的最短距离
bool vis[MAXN];                    // vis[i]表示i是否已确定最短路

void dijkstra() {                  // Dijkstra算法
    for (int i = 1; i <= n; i++) { // 初始化距离为无穷大
        dis[i] = INF;
    }
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;  // 小根堆
    
    dis[s] = 0;                    // 起点距离为0
    pq.push({0, s});               // 起点入队
    
    while (!pq.empty()) {          // 队列非空时循环
        int u = pq.top().second;   // 取出当前距离最小的点
        pq.pop();                  // 弹出堆顶
        
        if (vis[u]) continue;      // 如果已处理过则跳过
        vis[u] = true;             // 标记为已处理
        
        for (int i = head[u]; i; i = e[i].nxt) {  // 遍历u的所有出边
            int v = e[i].to;       // 边的终点
            long long w = e[i].w;  // 边的权值
            
            if (dis[u] + w < dis[v]) {  // 如果能更新最短路
                dis[v] = dis[u] + w;    // 更新距离
                pq.push({dis[v], v});   // 将v入队
            }
        }
    }
}

int main() {
    cin >> n >> m >> s;            // 读入点数、边数、起点
    
    for (int i = 0; i < m; i++) {  // 读入m条边
        int u, v;                  // 边的起点和终点
        long long w;               // 边的权值
        cin >> u >> v >> w;        // 读入边的信息
        addEdge(u, v, w);          // 添加有向边
    }
    
    dijkstra();                    // 运行Dijkstra算法
    
    for (int i = 1; i <= n; i++) { // 输出每个点的最短距离
        if (dis[i] == INF) {       // 如果不可达
            cout << -1;            // 输出-1
        } else {                   // 否则
            cout << dis[i];        // 输出最短距离
        }
        if (i < n) cout << " ";    // 点之间用空格分隔
    }
    cout << endl;                  // 输出换行
    
    return 0;
}