单源最短路之Dijkstra(迪杰斯特拉)算法
适用范围：没有负边
时间复杂度：O(|E|log|V|）
核心思想：
(1)找到最短距离已经确定的顶点中最短距离最小的顶点u，从它出发更新所有相邻顶点的距离
(2)然后就不需要关心u并重复(1)直到所有顶点的最短距离都确定了
/*题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2544 */
#include <queue>
#include <cstdio>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MAX_V 5050
using namespace std;
typedef struct node
{
int dis;
int num;
}P;
P a[MAX_V];
int V,E;
int cost[MAX_V][MAX_V];
bool operator<(const P &x,const P &y)
{
return x.dis>y.dis;
}
int dijkt(int s)
{
priority_queue<P> que;
for(int i=1;i<=V;i++)
{
a[i].num=i;
a[i].dis=INF;
}
a[s].dis=0;
que.push(a[s]);
while(!que.empty())
{
P tmp=que.top();
que.pop();
for(int i=1;i<=V;i++)
{
if(a[i].dis>tmp.dis+cost[tmp.num][i])
{
a[i].dis=tmp.dis+cost[tmp.num][i];
que.push(a[i]);
}
}
}
return a[V].dis;
}
int main()
{
while(scanf("%d%d",&V,&E))
{
if(V==0&&E==0)
break;
for(int i=1;i<=V;i++)
for(int j=1;j<=V;j++)
cost[i][j]=INF;
for(int i=1;i<=E;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
cost[x][y]=cost[y][x]=z;
}
printf("%d\n",dijkt(1));
}
return 0;
}
