题目描述

最短路

算法1

步骤：

1.初始化：起点到起点的距离为0，其他距离为正无穷
（1）n次迭代
t-< 每次迭代找到不在s中，且距离最近的点。
（2）将s[t]==true，即将t加入以确定最短距离的点中
（3）用t更新其他点到起点的距离

注意：s是当前以确定的最短距离的点

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=510;
int g[maxn][maxn];//邻接矩阵来存储 
int dis[maxn];//表示1-n的距离 
bool st[maxn];//看i是否已经确定了最短路径 
int n,m;

int distl(){
    memset(dis,0x3f3f3f3f,sizeof dis);//初始化 
    dis[1]=0;//初始化 
    for(int i=0;i<n;i++){ //n次迭代 
        int t=-1;
        for(int j=1;j<=n;j++){ //找没有确定的距离最短的点 
            if(!st[j]&&(t==-1||dis[t]>dis[j]))
            t=j;
        }
        if(t==n) break;//优化 说明已经找了n的最短路 
       st[t]=true;//将该点加入以确定的点 
       for(int j=1;j<=n;j++)//用t来更新其他顶点 
       dis[j]=min(dis[j],dis[t]+g[t][j]);   
    }
    if(dis[n]==0x3f3f3f3f)//说明没有通路 
    return -1;
    return dis[n];


}
int main(){
    cin>>n>>m;
    int a,b,c;
    memset(g,0x3f3f3f3f,sizeof g); 
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c);//因为有重边 取权重最小的 
    }
    cout<<distl()<<endl;
    return 0;
}