#include <iostream>#include <malloc.h>#include <cstring>#include <stack>#include <cstdio>//定义邻接矩阵的大小#define N 100#define M 100using namespace std;typedef struct node {int map[N][M];//邻接矩阵int n;//顶点数int e;//边数}MGragh;void dijkstra(MGragh g,int *dis,int *pre,int v0){int i,j,k;bool *visited=(bool *)malloc(sizeof(bool)*g.n);//标记数组for(i=0;i<g.n;i++){//初始化if(g.map[v0][i]>0&&i!=0){dis[i]=g.map[v0][i];pre[i]=v0;}else{dis[i]=INT_MAX;pre[i]=-1;}pre[v0]=v0;dis[v0]=0;}visited[v0]=true;//标记源点v0为访问过for(i=1;i<g.n;i++){//运行n-1次int min=INT_MAX;//初始化int u;for(j=0;j<g.n;j++){//寻找未访问过的顶点中权值最小的那个if(visited[j]==false&&dis[j]<min){min=dis[j];//记录下来u=j;}}visited[u]=true;//标记为访问过//更新dis数组的值和路径for(k=0;k<g.n;k++){if(visited[k]==false&&g.map[u][k]>0&&g.map[u][k]+min<dis[k]){dis[k]=min+g.map[u][k];pre[k]=u;}}}}void showpath(int *pre,int v,int v0){//v是当前节点，//输出源点v0到当前节点v的路径stack<int>s;while(v!=v0){s.push(v);v=pre[v];}s.push(v);while(!s.empty()){printf("%d ",s.top());s.pop();}}int main(){int n,e;while(scanf("%d%d",&n,&e)&&e!=0){int i,j;int s,t,w;//起始点s，，终点t，边st的权值为wMGragh g;int v0;//源点v0int *dis=(int *)malloc(sizeof(int)*n);//dis[i]记录从源点v0到当前点i的路径长度int *pre=(int *)malloc(sizeof(int)*n);//记录每个点的前驱，即pre[i]=j;说明i点的前驱为jfor(i=0;i<N;i++){//初始化for(j=0;j<M;j++){g.map[i][j]=0;}}g.n=n;g.e=e;for(i=0;i<e;i++){//建立邻接矩阵scanf("%d%d%d",&s,&t,&w);g.map[s][t]=w;}scanf("%d",&v0);dijkstra(g,dis,pre,v0);for(i=0;i<n;i++){if(i!=v0){showpath(pre,i,v0);//输出路径printf("%d\n",dis[i]);//输出最短路径的大小}}}return 0;}/*测试用例5 70 1 1000 2 300 4 102 1 602 3 603 1 104 3 500*/
版权声明：欢迎转载，转载时请在文章开头注明出处
以诚感人者，人亦诚而应。
