C++图论（第二弹）

元旦快乐呀！
祝大家2022心想事成、工作顺利！

今天我们继续来学习图论，和弗洛伊德算法。



来做一道案例：





根据以上内容可以推出：

注意：

因此可写代码：

//Author:PanDaoxi
#include 
using namespace std;
int e[101][101];
int n,m; //n=顶点数 m=边数
int p,q,t; //p=p点 q=q点 t=路程
int s=100001; 
int main(){
	cin>>n>>m; //输入顶点和边数
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j){
				e[i][j]=0; //如果点是当前位置，则距离为0 
			} 
			else{
				e[i][j]=s;
			}
		}
	} 
	//路程的设定
	for(int i=1;i<=m;i++){
		cin>>p>>q>>t;
		e[p][q]=t; //有向图  
	} 
	//弗洛伊德算法
	for(int k=1;k<=n;k++){
		//城市i到城市j的不同组合 
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				//判断最短路径
				if(e[i][j]>e[i][k]+e[k][j]){
					e[i][j]=e[i][k]+e[k][j];
				} 
			}
		}
	} 
	 
	//最短路径
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout< 
测试数据：
 
4 8
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5