啥都不是

原题链接：1.A+B problem
userId_undefined

张茗皓

倔强青铜

2023-07-29 13:23:35

发布于：江苏

5阅读
0回复
0点赞
#include<iostream>
#include<cstring>
using namespace std;
const int N=100;
int G[N][N];
int n,m;
void Print(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(G[i][j]==0x3f3f3f3f) cout<<"INF ";
			else printf("%3d ",G[i][j]);
		}
		cout<<"\n";
	}
	cout<<"============\n";
}
int main(){
	cin>>n>>m;
	memset(G,0x3f,sizeof(G));
	for(int i=1;i<=n;i++) G[i][i]=0;//自己到自己 
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		G[u][v]=w;//无向图 G[u][v]=G[v][u]=w;
	}
	Print();
	//G[i][k]+G[k][j] 是否比 G[i][j] 更短 
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(G[i][k]+G[k][j]<G[i][j]){
					G[i][j]=G[i][k]+G[k][i];
				}
//				G[i][j]=min(G[i][j],G[i][k]+G[k][i]);
			}
		}
	}
	Print();
	return 0;
}
/*
5 6
1 2 3
1 3 8
2 3 4
2 4 6
3 5 5
4 5 1
*/
userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论