HDU Today （最短路径问题）

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

代码：

#include <string>
#include <map>
#include <iostream>
using namespace std;
#define INF 0x3fffffff
#define MAXN 10017
#define M 32
int mat[MAXN][MAXN] ,n;
#define MAX 150
map<string,int>m;
void init()
{for(int i = 0; i <= MAX; i++){for(int j = 0; j <= MAX; j++){if(i == j)mat[i][j] = 0;elsemat[i][j] = INF;}}m.clear();
}int dijkstra (int s,int f)
{//s为起点， f：为终点int dis[MAXN];//记录到任意点的最短距离int mark[MAXN];//记录被选中的结点 int i,j,k = 0;for(i = 0; i <= MAX; i++){mark[i] = 0;//初始化所有结点，每个结点都没有被选中 dis[i] = INF;}mark[s] = 1;//start结点被选中 dis[s] = 0;//将start结点的的距离设置为0 int min ;//设置最短的距离。 for(i = 1; i <= MAX; i++){k = 1;min = INF;for(j = 1; j <= MAX; j++){if(mark[j] == 0  && dis[j] < min)//未被选中的结点中，距离最短的被选中 {min = dis[j] ;k = j;}}mark[k] = 1;//标记为被选中 for(j = 1; j <= MAX; j++){if( mark[j] == 0  && (dis[j] > (dis[k] + mat[k][j])))//修改剩余结点的最短距离 {dis[j] = dis[k] + mat[k][j];}}}return dis[f];    
} int main()
{int i;char s[M], e[M], a[M], b[M];int v;while(~scanf("%d",&n)){init();if(n == -1)break;scanf("%s%s",s,e);m[s] = 1;if(!m[e])m[e] = 2;int c = 3;for(i = 0; i < n; i++){scanf("%s%s%d",a,b,&v);if(!m[a])m[a] = c++;if(!m[b])m[b] = c++;if(v < mat[m[a]][m[b]]){mat[m[a]][m[b]] = v;mat[m[b]][m[a]] = v;}}int ans = dijkstra(m[s],m[e]);if(ans == INF)printf("-1\n");elseprintf("%d\n",ans);}return 0;
}

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

---