寒假专题训练--最短路

最短路

A - 最短路

[HDU - 2544]

• 题意
  求起点到终点的最短路。
• 思路
  加权最短路，取时间为路径的权重，为正数。迪杰斯特拉实现。
• 代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <stack>
#include <queue>
using namespace std;
#define INF 1000005
int n,m,dir,minx,now;
int used[155],sl[155],gra[155][155];
int be,st;
int main(){
    while(scanf("%d%d",&n,&m),n!=0&&m!=0){
        minx=INF;
        memset(sl,0,sizeof(sl));
        memset(used,0,sizeof(used));
        for (int i = 0; i < 155; ++i)
        {
            for (int j = 0; j < 155; ++j)
            {
                gra[i][j]=INF;
                if (i==j)
                {
                    gra[i][j]=0;
                }
            }
        }
        for(int i=0;i<m;i++){
            cin>>be>>st>>dir;
            if (gra[be][st]>dir)
            {
                gra[be][st]=dir;
                gra[st][be]=dir;//no direction
            }
        }
        if (n==1)
        {
            printf("0\n");
            continue;
        }
        for(int i=1;i<=n;i++){
            sl[i]=gra[1][i];
        }
        used[1]=1;
        now=1;
        //now must have initial value,if the begin point can't connect to others,
        for (int i = 2; i <= n; ++i)
        {
            minx=INF;
            for(int j=1;j<=n;j++){
                if (!used[j]&&sl[j]<minx)
                {
                    now=j;
                    minx=sl[j];
                }
            }
            used[now]=1;
            for (int j = 1; j <=n; ++j)
            {
                if (!used[j]&&sl[now]+gra[now][j]<sl[j])
                {
                    sl[j]=sl[now]+gra[now][j];
                }
            }
        }
        if (sl[n]<INF)
        {
            printf("%d\n",sl[n] );
        }else{
            printf("-1\n");
        }
    }
    return 0;
}