图
2025-01-09 23:27:30
发布于：北京
25阅读
0回复
0点赞
都是模板！！！
无向图的最短路径
Dijkstra 算法?
#include<bits/stdc++.h>
using namespace std;
#define ing long long
const int N = 1e3 + 10;
int dis[N],vis[N],e[N][N];
signed main(){
int n,m,s;
cin>>n>>m>>s;
while(m--){
int u,v,w;
cin >> u >> v >> w;
int tmp = e[u][v] ? e[u][v] : 1e9;
e[u][v] = min(tmp,w);
}
//1、初始化dis
for(int i = 0;i <= n; i++){
dis[i] = 1e9;
}
dis[s] = 0;
//2、n轮
for(int i = 1;i <= n; i++){
//3.1 没有确定最短路的点里面找 dis[u] 最小的点 u
int u = 0;
for(int j = 1;j <= n; j++){
if(!vis[j] && dis[j] < dis[u])
u = j;
}
//3。2 标记，确定 u 的最短路
vis[u] = 1;
//3.2 松弛 u 的邻接边
for(int j = 1;j <= n; j++){
if(e[u][j]){
int v = j;
int w = e[u][j];
if(dis[u] + w < dis[v]){
dis[v] = dis[u] + w;
}
}
}
}
for(int i = 1;i <= n; i++){
if(dis[i] != 1e9){
cout<<dis[i]<<" ";
}
else cout<<-1<<" ";
}
return 0;
}
Bellman-Ford 算法：
小码君的太空基地（填空）
#include<bits/stdc++.h>
using namespace std;
struct node{
int from , to,len;
}a[10010];
int n , m , w , x , y,z , s , t;
int d[10010] ;
int main(){
scanf("%d %d %d %d",&n,&m,&s,&t);
for(int i = 1;i <= n;i++){
d[i] = 1e9;
}
d[s] = 0;
for(int i = 1;i <= m;i++){
cin>>a[i].from>>a[i].to>>a[i].len;
}
int from , to , len;
for(int k = 1;k < n;k++){
for(int i = 1;i <= m;i++){
from = a[i].from,to=a[i].to,len = a[i].len;
//判断走到to这个点能否更新最短距离
if(d[from] + len < d[to]){
d[to] = d[from] + len;
}
}
}
//输出走到t的最少消耗氧气
cout<<d[t];
return 0;
}
SPFA 算法：
小码君的太空基地spfa
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
int u,v,w;// u————>v 权值是 w 的边
int mp[5005][5005];
int dis[5005];
int vis[5005];//标记一个点在不在队列
int main(){
cin >> n >> m >> s >> t;
for(int i = 1;i <= n;i++){
dis[i] = 1e9;
for(int j = 1;j <= n;j++){
mp[i][j] = 1e9;
}
}
while(m--){
cin >> u >> v >> w;
mp[u][v] = w;
}
//1、搞个队列，起点最短路距离改为 0，入队并标记
queue<int> q;
dis[s] = 0;
q.push(s);
vis[s] = 1;
//2、SPFA 启动！
while(!q.empty()){
//2.1、出队并取消标记
u = q.front();
q.pop();
vis[u] = 0;
//2.2、松弛以 u 为起点的边
for(int i = 1;i <= n;i++){
if(mp[u][i] != 1e9){
v = i;
w =mp[u][v];
if(dis[u] + w < dis[v]){//松弛
dis[v] = dis[u] + w;
if(vis[v] == 0){
q.push(v);
vis[v] = 1;
}
}
}
}
}
cout<<dis[t];
return 0;
}
Floyd 算法：
海盗宝藏
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;//计数器
int dis[101][101],a[10001];//距离数组及必经之路数组
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d",&a[i]);//输入必经之路
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&dis[i][j]);//输入距离
}
}
//将每个顶点作为中转点
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
//松弛操作
dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
}
}
}
for(int i=2;i<=m;i++){
//计数
ans+=dis[a[i-1]][a[i]];
}
printf("%d",ans);
return 0;
}
有帮助，赞一个