图

张子渝

2025-01-09 23:27:30

发布于：北京

35阅读

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;
}