Hud 1874 畅通工程续[基础最短路(Dijsktra)]

本文主要是介绍Hud 1874 畅通工程续[基础最短路(Dijsktra)]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一次的最短路，还可以吧！经过别人的提醒2A.

题目链接：点击打开链接

#include<cstdio>
#include<cstring>
using namespace std;
const int N=205;
const int INF=0xffffff;
int Map[N][N];
int n,m,dis[N];
bool vis[N];
void Init()
{for(int i=0;i<n;i++)for(int j=0;j<n;j++)Map[i][j]=INF;
}
void dijkstra(int u)
{//首先得初始化.memset(vis,0,sizeof(vis));vis[u]=true;for(int i=0;i<n;i++){if(i!=u) dis[i]=Map[u][i];else dis[i]=0;}for(int i=0;i<n;i++){int temp=INF,t=u;for(int j=0;j<n;j++)if(!vis[j]&&(dis[j]<temp)){temp=dis[j];t=j;}
//        printf("temp=%d\n",temp);
//        printf("-------------\n");if(t==u) break;vis[t]=true;for(int j=0;j<n;j++)if(!vis[j]&&Map[t][j]<INF&&dis[j]>(dis[t]+Map[t][j]))dis[j]=dis[t]+Map[t][j];}
}
int main()
{while(~scanf("%d%d",&n,&m)){Init();for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);if(Map[a][b]>c){Map[a][b]=c;Map[b][a]=c;}}int u,end;scanf("%d%d",&u,&end);dijkstra(u);if(dis[end]==INF) printf("-1\n");elseprintf("%d\n",dis[end]);}return 0;
}

这篇关于Hud 1874 畅通工程续[基础最短路(Dijsktra)]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---