hdu 2544 单源最短路径(邻接矩阵Dijkstra实现)

Problem: http://acm.hdu.edu.cn/showproblem.php?pid=2544

求商店到赛场最短时间

赤裸裸的单源最短路径

直接套最慢的邻接矩阵Dijkstra模版都0ms过

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 110
#define INF 1000000
int n,m,Map[MAXN][MAXN],Dist[MAXN];//Map[][]存图 ，Dist[]存最短路长 
void init(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)Map[i][j]=INF;
        Map[i][i]=0;
    }
    int a,b,c;
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&a,&b,&c);
        Map[a][b]=Map[b][a]=min(Map[a][b],c);//不知图中是否含有重复边，这样写保证就算有重复边也没关系 
    }
}
void Dijkstra(int s){
    bool Vis[MAXN];//Vis[]记录是否已求最短路 
    memset(Vis,false,sizeof(Vis));
    for(int i=1;i<=n;i++)Dist[i]=Map[s][i];
    Vis[s]=true;
    for(int i=1;i<n;i++){
        int Min=INF,k=0;
        for(int j=1;j<=n;j++)if(!Vis[j] && Dist[j]<Min){
            Min=Dist[j];
            k=j;
        }
        if(k==n)return;//因为题目只需要求1-n的最短路，多余的不用管了 
        Vis[k]=true;
        for(int j=1;j<=n;j++)if(!Vis[j] && Map[k][j]!=INF && Dist[j]>Dist[k]+Map[k][j])Dist[j]=Dist[k]+Map[k][j]//更新路径 
    }
}
int main()
{
    while(scanf("%d%d",&n,&m),n+m){
        init();
        Dijkstra(1);
        printf("%d
",Dist[n]);
    }
}

View Code

本来想写堆优化的Dijkstra的，但想想在这题上岂不大材小用浪费时间，上面已经写过一篇堆优化的Dijkstra了...可围观，>.<