今天研究了一下Dijkstra

效率比Floyd快多了Floyd:O(n^3) Dijkstra:O(n^2)
但是处理不了负权边QwQ
更主要的是，本蒟蒻不会优先队列优化QAQ
所以本模版的空间复杂度极高……
（有大佬教教本喵吗，求求了QwQ）

#include<iostream>
using namespace std;
//节点数量，边数量，起点编号； 
int n,m,s;
//邻接矩阵，最短路数组； 
int map[10001][10001],dis[10001];
//确认最短路数组； 
bool st[10001];
int main(){
    //输入 节点数量 边数量 起点编号； 
    scanf("%d %d %d",&n,&m,&s);
    //遍历 邻接矩阵的 一半（因为对角线对称）；
    for(int i=0;i<=n;i++){//对于 任意的 节点； 
        //从 自己 到 自己 的 距离 为 0；
        map[i][i]=0;
        //从 起点 到 该节点 的 最近距离 为 “无法到达”； 
        dis[i]=-1;
        for(int ii=0;ii<i;ii++){
            //从 任意节点 到 任意节点 的 距离 为 “无法到达”；
            map[i][ii]=map[ii][i]=-1;
        }
    }
    //从 起点 到 起点 的 最近距离 为 0；
    dis[s]=0;
    //从 起点 到 起点 已有最短路径； 
    st[s]=1;
    //输入 m条 边； 
    for(int i=0,A,B,C;i<m;i++){
        //输入 起点 终点 权值；
        scanf("%d %d %d",&A,&B,&C);
        //特判1：若有重边；
        if(map[A][B]>C || map[A][B]<0){
            map[A][B]=C;
        }//只保留↑较近的；
        //特判1：若是起点的出边；
        if(A==s &&(dis[B]>map[A][B] || dis[B]<0)){
            dis[B]=map[A][B];
        }//更新最短路↑；
    }
    //开始 更新 单源最短路 ；
    for(int i=1,clt,id=s;i<=n;i++){
        //遍历 所有 非 确认最短路的 节点； 
        for(int ii=1;ii<=n;ii++){
            //若 该点 确认最短路； 
            if(st[ii])continue;//跳过；
            //若 可以 间接到达 该点； 
            if(dis[id]>=0 && map[id][ii]>=0){
                //若 间接距离 比 直接距离 近； 
                if(dis[ii]>dis[id]+map[id][ii]){
                    //更新； 
                    dis[ii]=dis[id]+map[id][ii];
                //若 无法 直接到达； 
                }else if(dis[ii]<0){
                    //将 最近距离 改为 间接距离； 
                    dis[ii]=dis[id]+map[id][ii];
                }
            }//顺带一提，上面的操作有一个专业名称叫“松弛”； 
        }//这里没有钢门（划掉）；
        //将 最近距离 初始化为 “无法到达”； 
        clt=0x7fffffff;
        //遍历所有 已知最短路 但是 还未确认的 节点； 
        for(int ii=1;ii<=n;ii++){
            //若 该点 确认最短路；
            if(st[ii])continue;//跳过； 
            if(clt>dis[ii] && dis[ii]>=0){
                clt=dis[ii];
                id=ii;
            }
        }//选出 最短的 已知最短路↑；
        //将其 确认； 
        st[id]=1;
    }
    //开始 输出 距离； 
    for(int i=1;i<=n;i++){
        //若 不存在 最短路； 
        if(dis[i]<0){
            //DDDD;
            printf("Nope ");
        }else{//否则；
            //输出 最短距离； 
            printf("%d ",dis[i]);
        }
    }
    return/*结束*/0;
}

<z
^z

给本蒟蒻点个赞吧喵~