图结构练习——最短路径(dijkstra算法)

xiaoxiao2021-02-28  15

Problem Description

 给定一个带权无向图,求节点1到节点n的最短路径。  

Input

 输入包含多组数据,格式如下。 第一行包括两个整数n m,代表节点个数和边的个数。(n<=100) 剩下m行每行3个正整数a b c,代表节点a和节点b之间有一条边,权值为c。  

Output

 每组输出占一行,仅输出从1到n的最短路径权值。(保证最短路径存在)  

Example Input

3 2 1 2 1 1 3 1 1 0

Example Output

1 0

注意:最短路覆盖

#include<iostream> #include<stdio.h> #include <cstring> using namespace std; const int inf=99999999; int amap[105][105]; int book[105]; int dis[105]; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { if(m==0) { cout<<0<<endl; continue; } memset(book,0,sizeof(book)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(i==j)amap[i][j]=0; else amap[i][j]=inf; } for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; if(amap[x][y]>z) //避免覆盖最短路 amap[x][y]=amap[y][x]=z; } for(int i=1;i<=n;i++) //dis数组初始化 { dis[i]=amap[1][i]; } book[1]=1; for(int i=1;i<=n-1;i++) //1到n-1 { int amin=inf; int a; for(int j=1;j<=n;j++) { if(book[j]==0&&dis[j]<amin) { amin=dis[j]; a=j; } } book[a]=1; for(int i=1;i<=n;i++) { if(amap[a][i]<inf) { if(dis[i]>dis[a]+amap[a][i]) dis[i]=dis[a]+amap[a][i]; } } } cout<<dis[n]<<endl; } return 0; }

转载请注明原文地址: https://www.6miu.com/read-1650357.html

最新回复(0)