Void-7's

洛谷P3371 【模板】单源最短路径(弱化版)

单源最短路径 Single Source Shortest Path

Dijkstra算法

算法思想

初始化节点访问数组

设置d[0]=0; 其他d[i]=INF

循环n次{

​ 在所有未访问过的节点中,选出distance最短的节点x

​ 访问节点x

​ 对于节点x出发的所有边(x,y),更新d[y]=min(d[x]+w(x,y),d[y])

}

AC代码

#include<bits/stdc++.h>
#define inf 2147483647
using namespace std;
int n,m,s;
vector<pair<int,int> > g[10010];
//pair的first为(x,y)的y,second为边长
int dis[10010];//dis[i]:出发点[s]到点[i]的最短路径
int vis[10010];//vis[i]:是否访问过i (已经求过s到i的最短路径)

inline void add(int x,int y,int w){
    g[x].push_back(make_pair(y,w));
}

int main(){
    int u,v,z;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&z);
        add(u,v,z);
    }
    //init
    for(int i = 1; i <= n; i++) dis[i] = inf, vis[i] = 0;
    dis[s]=0;
    //core code
    for(int i=1;i<n;i++){
        //在所有未访问过的节点中,选出distance最短的节点x
        int min_val = inf;int min_i=0;
        for(int j=1;j<=n;j++){
            if(vis[j]) continue;
            if(!vis[j]&&dis[j]<min_val){
                min_val=dis[j];
                min_i=j;
            }
        }
        //访问节点x
        vis[min_i]=1;
        //对于节点x出发的所有边(x,y),更新d[y]=min(d[x]+w(x,y),d[y])
        int size=g[min_i].size();
        for(int k=0;k<size;k++){
            //weight & y of (x,y)
            int w=g[min_i][k].second,y=g[min_i][k].first;
            if((w+dis[min_i])<dis[y])
                dis[y]= w+dis[min_i];
        }
    }
    for(int i = 1; i <= n; i++) printf("%d ", dis[i]);
    return 0;
}

数据结构是邻接表,后面再使用链式前向星…… 目前时间复杂度O(n^2),待优化……