洛谷 模板 单源最短路径（标准版）

原题p4779

题目背景

2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程 一题里非常熟练地使用了一个广为人知的算法求最短路。

然后呢？

100→60；

Ag→Cu；

最终，他因此没能与理想的大学达成契约。

小 F 衷心祝愿大家不再重蹈覆辙。

题目描述

给定一个 n 个点，m 条有向边的带非负权图，请你计算从 s 出发，到每个点的距离。

数据保证你能从 s 出发到任意点。

输入格式

第一行为三个正整数 n,m,s。 第二行起 m 行，每行三个非负整数 ui​,vi​,wi​，表示从ui​ 到 vi​ 有一条权值为 wi​ 的有向边。

输出格式

输出一行 n 个空格分隔的非负整数，表示 s 到每个点的距离。

输入输出样例

输入 #1

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

输出 #1

0 2 4 3

说明/提示

fill函数用法

赋初值：fill(l ,r , num) 意为给[l,r-1]区间赋值num

超时代码

时间复杂度 O(n^2)

#include <iostream>  // 引入输入输出流库   
#include <algorithm> // 引入算法库（本例中主要为了使用fill函数）  
using namespace std; 
  
const int N = 1E5 + 5; // 定义节点数上限  
const int M = 2E5 + 5; // 定义边数上限  
int n, m, s;           // 分别表示节点数、边数和起点  
  
struct edge {          // 定义边结构体  
    int d;             // 边的权重  
    int to;            // 边的终点  
    int next;          // 链表的下一个节点索引  
} e[M];                // 定义边数组  
  
int dis[N], h[N], cnt; // 分别表示距离数组、邻接表头节点数组和边计数器  
bool vis[N];           // 标记节点是否已被访问  
  
// 查找当前未访问节点中距离最小的节点索引  
int min_dis() {    
    int min = 0x7fffffff, min_idx = 0;    
    for (int i = 1; i <= n; i++) {    
        if (!vis[i] && min > dis[i]) {    
            min = dis[i];    
            min_idx = i;    
        }    
    }    
    return min_idx;    
}    
  
// 向邻接表中添加边  
void add(int u, int v, int d) {    
    cnt++;    
    e[cnt].to = v;    
    e[cnt].d = d;    
    e[cnt].next = h[u];    
    h[u] = cnt;    
}    
  
// 执行Dijkstra算法计算最短路径  
void Dijkstra() {    
    fill(dis + 1, dis + n + 1, 0X7fffffff); // 初始化距离数组为正无穷大  
    dis[s] = 0;  // 起点到自身的距离为0  
        
    for (int i = 1; i <= n; i++) {    
        int k = min_dis();  // 找到当前未访问节点中距离最小的节点  
        vis[k] = true;  // 标记该节点为已访问  
        for (int j = h[k]; j; j = e[j].next) {  // 遍历该节点的所有邻接边  
            int y = e[j].to;  // 邻接边的终点  
            if (!vis[y] && dis[y] > dis[k] + e[j].d) {  // 如果该节点未访问且通过当前节点到达它的距离更短  
                dis[y] = dis[k] + e[j].d;  // 更新距离  
            }    
        }    
    }    
}    
  
int main() {    
    cin >> n >> m >> s;  // 输入节点数、边数和起点  
    for (int i = 1; i <= m; i++) {    
        int u, v, d;    
        cin >> u >> v >> d;  // 输入每条边的起点、终点和权重  
        add(u, v, d);  // 向邻接表中添加边  
    }    
    Dijkstra();  
    for (int i = 1; i <= n; i++) {    
        if (dis[i] != 0X7fffffff) cout << dis[i] << " ";  // 输出每个节点的最短距离（排除正无穷大）  
    }    
    cout << endl;    
    return 0;    
}

AC代码

时间复杂度O((n+m)log​n)

#include <iostream>  
#include <queue>  
#include <algorithm>  
using namespace std;  
  
const int N = 1E5 + 5;   
const int M = 2E5 + 5; 
int n,m,s; 
struct edga { 
    int d;       
    int to;    
    int next;  
} e[M];  
  
int dis[N], h[N], cnt; 
bool vis[N];           
  
// 自定义节点结构体，用于优先队列  
struct node {  
    int pos;  // 节点位置  
    int dis;  // 从起点到该节点的距离  
    // 重载小于运算符，使得优先队列按照距离从小到大排序  
    bool operator <(const node &x) const {  
        return x.dis < dis;  
    }  
};  
  
priority_queue<node> q; // 优先队列，用于存储待处理的节点及其距离  
  
// 向邻接表中添加边  
void add(int u, int v, int d) {  
    cnt++;  
    e[cnt].to = v;  
    e[cnt].next = h[u];  
    e[cnt].d = d;  
    h[u] = cnt;  
}  
   
void Dijkstra() {  
    dis[s] = 0;  
    q.push({s, 0});   
    while (!q.empty()) {  
        node temp = q.top(); 
        q.pop();  
        int x = temp.pos, d = temp.dis;  
        if (vis[x]) continue; 
        vis[x] = 1; 
        for (int i = h[x]; i; i = e[i].next) {  
            int y = e[i].to;  
            dis[y] = min(dis[y], e[i].d + d);   
            if (!vis[y]) q.push({y, dis[y]});
        }  
    }  
}  
  
int main() {  
    cin >> n >> m >> s; 
 	fill(dis + 1, dis + n + 1, 0X7fffffff);  
    for (int i = 1; i <= m; i++) {  
        int u, v, d;  
        cin >> u >> v >> d;  
        add(u, v, d);  
    }  
    Dijkstra();   
    for (int i = 1; i <= n; i++) {  
        if (dis[i] != 0x7fffffff) printf("%d ", dis[i]);  
    }  
    return 0;
}