最短路径Dijkstra算法模板题---洛谷P3371 【模板】单源最短路径（弱化版）

题目背景

本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入格式

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。

输出格式

一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）

输入输出样例

输入 #1复制

输出 #1复制

0 2 4 3

说明/提示

时空限制：1000ms,128M

数据规模：

对于20%的数据：N<=5，M<=15；

对于40%的数据：N<=100，M<=10000；

对于70%的数据：N<=1000，M<=100000；

对于100%的数据：N<=10000，M<=500000。保证数据随机。

对于真正 100% 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。

样例说明：

图片1到3和1到4的文字位置调换

过程：每次选择当前已经确定最短路径的点，作为起点，然后扩展路径，每个结点都做更新记录最短路径长度。N个结点，一共扩展N次

AC代码兼模板

#include <iostream>

#include <vector>

using namespace std;

const int NN = 1e4+;

const int inf = ;

int N,M,S;

struct node{

    int v,w;

};

vector<node> ve[NN]; //使用邻接表来存图

bool flag[NN];//flag[i] = 1 表示结点i已经作为了起点了

int dis[NN]; //存储起点到各结点的最短距离长度

void Dijkstra(int s){

    dis[s] = ;

    flag[s] = true;

    int t = N;

    while(t--){

        for(auto no: ve[s]){ //遍历以s为起点的边

            if(!flag[no.v]){

                dis[no.v] = min(dis[no.v],dis[s] + no.w); //更新路径最小值

            }

        }

        int minlen = inf;

        for(int i = ;i<=N;i++){ //寻找下一个起点

            if(!flag[i] && dis[i] < minlen){

                minlen = dis[i];

                s = i;

            }

        }

        flag[s] = true;//标记已经作为了起点

    }

}

int main(){

    cin>>N>>M>>S;

    for(int i = ;i<=N;i++) dis[i] = inf;

    int s,e,w;

    for(int i = ;i<=M;i++){

        scanf("%d%d%d",&s,&e,&w);

        ve[s].push_back({e,w});

    }

    Dijkstra(S);

    for(int i = ;i<=N;i++) printf("%d ",dis[i]);cout<<endl;

    return ;

}

巴特西