题目信息
- https://www.luogu.com.cn/problem/P4779
- 题解：https://www.luogu.com.cn/problem/solution/P4779
参考资料
- 最短路
- https://oi-wiki.org/graph/shortest-path/
自己挖坑
- 冷知识：
const int INF = 1e10;
虽然1e10超出了int的范围，但他会自动强制转换成int的最大边界值，不会爆
编译时添加 -Wall 指令
暂时不会用，交给老码农帮我去整理。。。
坑点
代码语言：javascript复制if (dist[k] i.l < dist[i.to] && dist[k] i.l > 0) {
dist[i.to] = dist[k] i.l;
ds.emplace(dist[i.to], i.to);
}
这里实际上是
代码语言：javascript复制dist[k] i.l >= 0
少写了一个=，当然这个条件其实不加也能AC
最后：谢谢各位神犇指教
题目背景
2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程 一题里非常熟练地使用了一个广为人知的算法求最短路。
然后呢？
100→60；
Ag→Cu；
最终，他因此没能与理想的大学达成契约。
小 F 衷心祝愿大家不再重蹈覆辙。
题目描述
给定一个 n 个点，m 条有向边的带非负权图，请你计算从 s 出发，到每个点的距离。
数据保证你能从 s 出发到任意点。
输入格式
第一行为三个正整数 n,m,s。第二行起 m 行，每行三个非负整数
，表示从
到
有一条权值为
的有向边。
输出格式
输出一行 n 个空格分隔的非负整数，表示 s 到每个点的距离。
输入输出样例
输入 #1复制
代码语言：javascript复制4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出 #1复制
代码语言：javascript复制0 2 4 3
说明/提示
样例解释请参考 数据随机的模板题。
；
；
- s=1；
；
,
。
本题数据可能会持续更新，但不会重测，望周知。
2018.09.04 数据更新 from @zzq
WA代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
#define endl 'n';
struct shortest_path {
struct edge {
int to;
int l;
};
const int INF = 1e10;
vector<int> dist;
vector<bool> b;
vector<vector<edge>> g;
shortest_path(int n) :
dist(n 1, INF), g(n), b(n, false) {}
void dijkstra (int n, int m, int s) { //单源最短路径,(负环会爆!)
for (int i = 0; i < m; i) { //存储边的情况
int u, v, w;
cin >> u >> v >> w;
--u;
--v;
g[u].push_back({v, w});
}
dist[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> ds;
ds.emplace(0, s);
while (!ds.empty()) {
auto k = ds.top().second;
ds.pop();
if (b[k]) {
continue;
}
for (auto i : g[k]) {
if (dist[k] i.l < dist[i.to] && dist[k] i.l > 0) {
dist[i.to] = dist[k] i.l;
ds.emplace(dist[i.to], i.to);
}
}
b[k] = true;
}
for (int i = 0; i < n; i) {
cout << dist[i] << " ";
}
}
};
void best_coder() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, s;
cin >> n >> m >> s;
shortest_path sp(n);
sp.dijkstra(n, m, s - 1);
}
void happy_coder() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
int main() {
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}
AC代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
#define endl 'n';
struct shortest_path {
struct edge {
int to;
long long l;
};
const long long INF = 1e17;
vector<long long> dist;
vector<bool> b;
vector<vector<edge>> g;
shortest_path(int n) :
dist(n 1, INF), g(n), b(n, false) {}
void dijkstra (int n, int m, int s) {
for (int i = 0; i < m; i) {
int u, v, w;
cin >> u >> v >> w;
--u;
--v;
g[u].push_back({v, w});
}
dist[s] = 0;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> ds;
for (int i = 0; i < n; i) {
ds.emplace(dist[i], i);
}
while (!ds.empty()) {
auto k = ds.top().second;
ds.pop();
if (b[k]) {
continue;
}
for (auto i : g[k]) {
if (dist[k] i.l < dist[i.to]) {
dist[i.to] = dist[k] i.l;
ds.emplace(dist[i.to], i.to);
}
}
b[k] = true;
}
for (int i = 0; i < n; i) {
cout << dist[i] << " ";
}
}
};
void best_coder() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, s;
cin >> n >> m >> s;
shortest_path sp(n);
sp.dijkstra(n, m, s - 1);
}
void happy_coder() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
int main() {
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}
