本文主要是介绍hdu1847畅通工程续，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
就是求两点间的最短距离。
解题思路：
不过我们发现顶点数要远远小于边的数目，所以我用dijkstra做的！
#include<stdio.h>
#define N 210
#define inf 1<<31-1
int mp[N][N];
int dis[N];
bool S[N];
void dijkstra(int st,int ed,int n){int i,j,mmax,k;for(i=0;i<n;i++)dis[i]=mp[st][i];dis[st]=0;S[st]=true;for(i=0;i<n;i++){mmax=inf;for(j=0;j<n;j++){if(!S[j]&&dis[j]<mmax){k=j;mmax=dis[j];}}S[k]=true;if(S[ed]){i=n+1;continue;}for(j=0;j<n;j++){if(dis[j]>dis[k]+mp[k][j])dis[j]=dis[k]+mp[k][j];}}}
void initi(int n){int i,j;for(i=0;i<n;i++){S[i]=false;dis[i]=inf;for(j=0;j<n;j++)mp[i][j]=inf;}
}
int main()
{int n,m,i,a,b,d,st,ed;while(scanf("%d%d",&n,&m)!=EOF){initi(n);for(i=0;i<m;i++){scanf("%d%d%d",&a,&b,&d);if(d<mp[a][b])mp[a][b]=mp[b][a]=d;}scanf("%d%d",&st,&ed);dijkstra(st,ed,n);if(dis[ed]==inf)puts("-1");elseprintf("%d\n",dis[ed]);}return 0;
}
这篇关于hdu1847畅通工程续的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
