U6-C2-dijkstra
原题链接：67324.4.0U5笔记合集
2025-11-15 17:30:48
发布于：江苏
16阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m, s;
int dis[N], g[N][N], vis[N];
int main(){
cin >> n >> m >> s;
//1、初始化 //输入m条边
for (int i=1; i<=m; i++){
int u, v, w;
cin >> u >> v >> w;
int t = g[u][v] ? g[u][v] : 1e9; //如果g[u][v]不为0那么就为1e9
g[u][v] = min(w, t); //选择重边中的最小值
}
for (int i=0; i<=n; i++) dis[i] = 1e9;
dis[s] = 0;//起点距离为 0
//dijkstra
for (int i=1; i<=n; i++){
//step1：找到距离起始点最小的顶点
int u = 0;
for (int j=1; j<=n; j++){
if (vis[j]==0 && dis[j]<dis[u]) u = j;
}
//step2：标记中转点然后开始松弛操作
vis[u] = 1;//将u作为中转点， 更新与u相连的所有点
for (int j=1; j<=n; j++){
if (g[u][j]){
int v = j;
int w = g[u][j];
//起始点到j的距离可以不可以通过u来松弛？
if (dis[v] > dis[u] + w){
dis[v] = dis[u] + w; //更新最短路
}
}
}
}
//输出
for (int i=1; i<=n; i++)
if (dis[i] != 1e9) cout<<dis[i]<<' ';
else cout << -1 << ' ' ;
return 0;
}
#if 0
dijkstra
迪杰斯特拉 算法
2、松弛操作（更新数组）
[单源最短路径1]
题目描述
给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
提示
1<=n,m<=1000,1<=u,v<=n,1<=w<=1000
输入格式
第一行包含三个整数n,m,s，分别表示点的个数、有向边的个数、出发点的编号。
接下来 m 行每行包含三个整数 u,v,w，表示一条u->v的，长度为w 的边。
输出格式
输出一行 n 个整数，第 i 个表示s 到第i 个点的最短路径，若不能到达则输出?1。
样例组
输入#1
输出#1
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
0 2 4 3
#endif
全部评论 2
void spfa(){
queue<int> q;
memset(d,1e6,sizeof d);
memset(vis,false,sizeof vis);
d[s] = 0;
vis[s] = 1;
q.push(s);while (q.size()) { int u = q.front(); q.pop(); vis[u] = 0; //注意, 拿出来的下次可以继续走 //枚举终点,更新距离 for (int i=1; i<=n; i++) { if (d[i] > d[u] + g[u][i]){ d[i] = d[u] + g[u][i]; //松弛,更新最短路 if (vis[i] == 0){ vis[i] = 1; //标记已经走过 q.push(i); } } } }}
2025-11-29 来自 江苏
0
有帮助，赞一个