[数据结构与算法]Dijkstra算法模板（HDU-2554）

分析

本题是典型的Dijkstra算法，唯一需要注意的是这是一个双向的图，两点之间双向都要赋值，当然在案例中也给出了。
Dijkstra算法的详细分析以及推理可以看 Dijkstra求最短路 I
来自AcWing的849. Dijkstra求最短路 I的一篇题解， 其中唯一需要解释的点

  for(int i=0;i<n;i++)      //有n个点所以要进行n次 迭代
  {
      int t=-1;       //t存储当前访问的点

      for(int j=1;j<=n;j++)   //这里的j代表的是从1号点开始
          if(!st[j]&&(t==-1||dist[t]>dist[j]))     
              t=j;

      st[t]=true;   

      for(int j=1;j<=n;j++)           //依次更新每个点所到相邻的点路径值
          dist[j]=min(dist[j],dist[t]+g[t][j]);
  }

在该模板算法中，这个双重循环中，第一个for循环是为了更新各个dist[N] 的值，其中第一次for循环是为了让dist[n]表示第n点到第1点的距离，之后的n次是为了更新最近的值，其中st[N]将每次确定的距离最近的点给标记了，从而在下次循环中不会再出现。

好了，接下来放改题的题解，唯一改动在于邻接矩阵赋值

AC代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=110;

int g[N][N];
int dist[N];
int st[N];
int n,m;
int dijkstra()
{
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	
	for(int i=1;i<n;i++)
	{
		int t=-1;
		for(int j=1;j<=n;j++)
		{
			if(!st[j]&&((t==-1)||dist[t]>dist[j]))
			t=j;
		}
		
	st[t]=1;
	for(int i=1;i<=n;i++)
	{
		 dist[i]=min(dist[i],dist[t]+g[t][i]);
		
	}
	}
	return dist[n];
}

int main()
{
	int x,y,z;
	
	while(cin>>n>>m,n||m)
	{
		
	memset(g,0x3f,sizeof g);
	memset(st,0,sizeof st);
	while(m--)
	{
		
		cin>>x>>y>>z;
		g[x][y]=g[y][x]=min(g[x][y],z);
		
	}
		 if(dijkstra()==0x3f3f3f3f)
		 cout<<-1<<endl;
		 else
		 cout<<dist[n]<<endl;
		}	 
		 return 0;
}