题目描述

dijkstra朴素算法

C++ 代码

```

include[HTML_REMOVED]

using namespace std;

const int N=510;//纯属搞笑

int n,m;//点与边

int x,y,z;//从x-y有1条有向边

int bian[N][N];//储存边

int jl[N];//每个点到第一个点的距离

bool fw[N];//记录该点最短距离是否已经确定

int dijkstra() //dijkstra

{

memset(jl,0x3f,sizeof jl);

jl[1]=0; //1到自身的距离

for(int i=0;i<n;i++) //从1点到n点距离枚举

{

    int t=-1;//刚开始标记为-1，储存当前访问的点

    for(int j=1;j<=n;j++) //从1号点开始比较

    {

        if(fw[j]==false&&(t==-1||jl[t]>jl[j])) //如果这个点没有被访问过 且刚开始访问 或 j点到i点的距离比t点到i点距离近

        {

            t=j;//那么最短距离定位从j点到i点的距离

        }

    }

    fw[t]=true;//记录已经被访问过的点

    for(int j=1;j<=n;j++) //从1到n枚举记录

    {

        jl[j]=min(jl[j],jl[t]+bian[t][j]); //是距离j小 还是 距离t加上距离t到j的距离小

    }

}

if(jl[n]==1061109567) return -1;  //如果第n个点路径为无穷大即不存在最低路径

return jl[n];  //返回

}

int main()

{

cin>>n>>m;

memset(bian,0x3f,sizeof bian);

//初始化<-

for(int i=1;i<=m;i++) //输入

{

    cin>>x>>y>>z;//从x-y有一条为z的有向边

    bian[x][y]=min(bian[x][y],z);//判断是否是自环

}

cout<<dijkstra()<<endl;

return 0;

}