迪杰斯特拉算法_模板

迪杰斯特拉算法模板

#include<cstdio> 

#include<iostream> 

#include<cstring> 

#include<algorithm> 

using namespace std; 

const int n=105; 

#define inf 1e6 

int a[n][n],d[n],vis[n],n; 

 ///用dijkstra算法找出城市1到其他城市的最小时间，然后取其中最大值

void dij() 

{ 

    memset(vis,0,sizeof(vis)); 

    for(int i=1; i<=n; i++) 

        d[i]=a[1][i]; 

    d[1]=0; 

    int i,j,u,v,min; 

    for(i=1; i<=n; i++) 

    { 

        min=inf; 

        for(u=1; u<=n; u++) 

        { 

            if(!vis[u]&&d[u]<min) 

            { 

                min=d[u]; 

                v=u; 

            } 

        } 

        if(min==inf) break; 

        vis[v]=1; 

            if(!vis[u]) 

                d[u]=min(d[u],d[v]+a[v][u]); 

    } 

    int ans=d[1]; 

        ans=max(ans,d[i]); 

    printf("%d\n",ans); 

}