hdu2544（单源最短路径）

本文主要是介绍hdu2544（单源最短路径），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

模板题：

//题意：求1到n的最短路径，模板题#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define N 105
#define inf 0x7ffffff
#define eps 1e-9
#define pi acos(-1.0)
#define P system("pause")
using namespace std;
int mp[N][N],vis[N],dist[N];
int n,m;
void dijkstra(int s)
{memset(vis,0,sizeof(vis));int i,j;for(i = 1; i <= n; i++)dist[i] = mp[s][i];dist[s] = 0;vis[s] = 1;for(i = 0 ;i < n-1; i++){int k,minn = inf;for(j = 1; j <= n; j++)if(!vis[j] && minn > dist[j]){k = j;minn = dist[j];}vis[k] = 1;for(j = 1; j <= n; j++)if(!vis[j] && dist[j] > dist[k] + mp[j][k])dist[j] = dist[k] + mp[j][k];}
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);while(scanf("%d%d",&n,&m)){if(!n && !m) break;int i, j;for(i = 1; i <= n; i++)for(j = 1; j <= n; j++)mp[i][j] = mp[j][i] = inf;for(i = 0; i < m; i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);if(mp[x][y] > z)mp[x][y] = mp[y][x] = z;}dijkstra(1);printf("%d\n",dist[n]);}return 0;
}
/*
3 3
1 2 4
1 2 2
2 3 3
*/

这篇关于hdu2544（单源最短路径）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---