【模板】单源最短路径(标准版)
题目描述
给定一个 n n n 个点, m m m 条有向边的带非负权图,请你计算从 s s s 出发,到每个点的距离。
数据保证你能从 s s s 出发到任意点。
输入格式
第一行为三个正整数 n , m , s n, m, s n,m,s。
第二行起 m m m 行,每行三个非负整数 u i , v i , w i u_i, v_i, w_i ui,vi,wi,表示从 u i u_i ui 到 v i v_i vi 有一条权值为 w i w_i wi 的有向边。
输出格式
输出一行 n n n 个空格分隔的非负整数,表示 s s s 到每个点的距离。
样例 #1
样例输入 #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
提示
1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105;
1 ≤ m ≤ 2 × 1 0 5 1 \leq m \leq 2\times 10^5 1≤m≤2×105;
s = 1 s = 1 s=1;
1 ≤ u i , v i ≤ n 1 \leq u_i, v_i\leq n 1≤ui,vi≤n;
0 ≤ w i ≤ 1 0 9 0 \leq w_i \leq 10 ^ 9 0≤wi≤109,
0 ≤ ∑ w i ≤ 1 0 9 0 \leq \sum w_i \leq 10 ^ 9 0≤∑wi≤109。
原题
洛谷P4779——传送门
(图片来源网络,侵删)
代码
#include using namespace std; #define max_Heap(x) priority_queue #define min_Heap(x) priority_queue typedef long long ll; typedef unsigned long long ull; typedef pair PII; typedef pair PLL; const double PI = acos(-1); const int maxn = 1e5 + 6; const int maxm = 5e5 + 6; struct edge { int to, len; // to为边的指向,len为边的长度即边权 }; vector e[maxn]; // 存储以点i为起点的边 struct node { ll dis; // dis为目前到该点的最短路长度 int num; // num为该点序号 bool operator>(const node &a) const // 小根堆中的大于号重载 { return dis > a.dis; } }; ll minDis[maxn]; // 从起点到第i个点的最短路长度 bool vis[maxn]; // 第i个点是否已确定最短路长度 priority_queue pq; // 还未确定最短路长度的点存放在小根堆中 void dijkstra(int n, int s) // n为点的个数,s为起点 { memset(minDis, 0x3f, sizeof(minDis)); // 将最短路距离初始化为无穷大 minDis[s] = 0; // 起点到起点的最短路长度为0 pq.push({0, s}); while (!pq.empty()) { int u = pq.top().num; // 有向边的起点 pq.pop(); if (vis[u]) // 若该点已确定最短路长度,跳过 continue; vis[u] = 1; for (edge eg : e[u]) // 遍历以该点为起点的所有有向边 { int v = eg.to; int w = eg.len; if (minDis[v] > minDis[u] + w) // 更新最短路长度 { minDis[v] = minDis[u] + w; pq.push({minDis[v], v}); } } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, s; // 点的个数,有向边的个数,出发点的编号 cin >> n >> m >> s; int u, v, w; // 从u到v的权值为w的有向边 while (m--) { cin >> u >> v >> w; e[u].push_back({v, w}); } dijkstra(n, s); for (int i = 1; i if (i != n) cout
文章版权声明:除非注明,否则均为VPS857原创文章,转载或复制请以超链接形式并注明出处。
还没有评论,来说两句吧...