题目描述如图所示: 

#include<stdio.h>//floyd算法求解最短路径问题，注解此法可以求解出所有节点之间的最短路径问题，如果在没有oj要求的基础上此方法非常实用而且简单
#include<string.h>
#include<vector>
using namespace std;
#define N 100
int main(){
	int ans[N][N];
    vector<int> E[N][N];
	int m,n,s,t;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
		   ans[i][j]=-1;//初始化-1代表无穷大
		}
	}
	FILE *fp1,*fp2;
	fp1=fopen("5.in","r");
	fp2=fopen("5.out","w");
    fscanf(fp1,"%d%d%d%d",&n,&m,&s,&t);//输入第一行数据n个城市m条道路，求出从s到t的最短路径
    while(m--){//将已知边的信息输入到邻接矩阵中
	   int x,y,z;
	   fscanf(fp1,"%d%d%d",&x,&y,&z);
	   ans[x][y]=z;
	}
	for(int k=1;k<=n;k++){//o(n^3)时间复杂度
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
			   if(ans[i][k]==-1||ans[k][j]==-1)continue;
			   if(ans[i][j]==-1||ans[i][k]+ans[k][j]<ans[i][j]){//如果满足要求则更新路径信息
			       ans[i][j]=ans[i][k]+ans[k][j];
				   E[i][j].push_back(k);//将路径信息保存到对应值里面
			   }
			}
		}
	}
	fprintf(fp2,"%d到%d的最短路径为:%d\n",s,t,ans[s][t]);
	fprintf(fp2,"%d ",s);//输出起点
	for(int h=0;h<E[s][t].size();h++){
	    fprintf(fp2,"%d ",E[s][t][h]);//输出中间路径
	}
	fprintf(fp2,"%d ",t);//输出终点
	fclose(fp1);
	fclose(fp2);
return 0;
}