最短路问题（模板题）

采用Floyd算法（插点）

• 首先输入，将各个站点的距离用邻接矩阵G[][]储存。这里需要注意的是（坑点），题目可能会多次输入两个站点之间的距离，这个距离我们需要取它们之中的最小值（所以将G[][]初始为无穷大）
• 接着进行初始化，将站点间自己到自己的路径长度设为0
• 插点，将每两个站点间路径，和将其他站点插入两站点之间的路径进行比较，如果插入后的路径更短，则更新两站点间的最短路径
• 输出G[s][t]即可，无法到达则输出-1

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e3+5;

int n,m,s,t,a,b,v,G[maxn][maxn];
void Floyd()
{
	//初始化
	for(int i=1;i<=n;i++){//自己到自己
		G[i][i]=0;
	} 
	//插点
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(G[i][j]>G[i][k]+G[k][j]){//与插入后进行比较
					G[i][j]=G[i][k]+G[k][j];
				}
			}
		}
	} 
}

int main()
{
	//输入 
	cin>>n>>m>>s>>t;
	memset(G,inf,sizeof(G));
	while(m--){
		cin>>a>>b>>v;
		G[a][b]=min(G[a][b],v);
		G[b][a]=G[a][b];
	}
	Floyd();
    //输出
    if(G[s][t]==inf)//无法到达
        cout<<"-1"<<endl;
    else//可以到达
	   cout<<G[s][t]<<endl;
    return 0;
}