首页 > 其他分享 >从 s 点到 t 点的最短路(简单模板)(迪杰斯特拉)

从 s 点到 t 点的最短路(简单模板)(迪杰斯特拉)

时间:2023-02-14 13:00:55浏览次数:47  
标签:dj int 短路 迪杰 vis 405 gra 模板

迪杰斯特拉简单版

#include <bits/stdc++.h>

using namespace std;

int m,n;
const int inf = 0x3f3f3f3f;
int dis[1005];
int gra[405][405];
int vis[1005];
void dj(int s, int t)
{
    memset(vis,0,sizeof(vis));
    int minn, v;
    for(int i = 0; i < n; i ++)
        dis[i] = gra[s][i];
    for(int i = 1; i <= n; i ++)
    {
        minn = inf;
        for(int j = 0; j < n; j ++)
        {
            if(!vis[j] && dis[j] < minn)
            {
                v = j;
                minn = dis[j];
            }
        }
        vis[v] = 1;
        for(int j = 0; j < n; j ++)
        {
            if(gra[v][j] + dis[v] < dis[j] && !vis[j])
            {
                dis[j] = gra[v][j] + dis[v];
            }
        }
    }
    if(dis[t] == inf)printf("-1\n");
    else printf("%d\n",dis[t]);
}
int main()
{
    int i, j, a, b, c, s, t;
    while(~scanf("%d%d", &n, &m))
    {
        for(i = 0; i < n; i ++)
        {
            for(j = 0; j < n; j ++)
            {
                if(i == j)
                    gra[i][j] = 0;
                else
                    gra[i][j] = gra[j][i] = inf;
            }
        }
        for(i = 1; i <= m; i ++)
        {
            scanf("%d%d%d", &a, &b, &c);
            if(gra[a][b] > c)
                gra[a][b] = gra[b][a] = c;
        }
        scanf("%d %d",&s,&t);
        dj(s,t);
    }
    return 0;
}

 

标签:dj,int,短路,迪杰,vis,405,gra,模板
From: https://blog.51cto.com/u_15965659/6056631

相关文章

  • vue原理:diff、模板编译、渲染过程等
    一、虚拟DOM:因为DOM操作非常消耗性能,在操作DOM时,会出现DOM的回流(Reflow:元素大小或者位置发生改变)与重绘(元素样式的改变)使DOM重新渲染。现在的框架Vue和React很少直接操作......
  • vue原理:diff、模板编译、渲染过程等
    一、虚拟DOM:因为DOM操作非常消耗性能,在操作DOM时,会出现DOM的回流(Reflow:元素大小或者位置发生改变)与重绘(元素样式的改变)使DOM重新渲染。现在的框架Vue和React很少直接操作......
  • Mybatis05 - 将有固定格式的文件添加至IDEA模板
    将常用的固定格式的配置文件添加为IDEA中的模板Mybatis核心配置文件mybatis-config.xmlMybatis映射文件mybatis-mapper.xml可以在新建文件时直接使用添加的模板红......
  • 最长公共子序列(模板 LCSL)
    博客: https://www.cnblogs.com/sasuke-/p/5396843.html模板#include<iostream>#include<cstdio>#include<cstring>#defineMAXN1010usingnamespacestd;intc[MAXN][M......
  • hamilton路径-图论算法模板
    什么是哈密尔顿路径哈密顿图(哈密尔顿图)(英语:Hamiltoniangraph,或Traceablegraph)是一个无向图,由天文学家哈密顿提出,由指定的起点前往指定的终点,途中经过所有其他节点且只经过......
  • 04 模板层
    模板层语法变量相关的用{{}},逻辑相关的用{%%}。注释:后端给模板传值及模板展示方式1:通过字典的键值对,指名道姓的一个个的传returnrender(request,'reg.html',{'n':n,......
  • 最短路
    最短路题目描述本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。如下图所示,G是一个无向图,其中蓝色边的长度是1、橘色边的长度是2、绿色边的长......
  • 基于Astar算法的栅格地图目标最短路径搜索算法MATLAB仿真,带GUI界面
    1.算法描述Astar算法是一种图形搜索算法,常用于寻路。它是个以广度优先搜索为基础,集Dijkstra算法与最佳优先(bestfit)算法特点于一身的一种算法。它通过下面这个函数来......
  • 基于GA算法的TSP最短路径搜索matlab仿真
    1.算法描述(1)编码:将问题的候选解用染色体表示,实现解空间向编码空间的映射过程。遗传算法不直接处理解空间的决策变量,而是将其转换成由基因按一定结构组成的染色体。编码方式......
  • 基于Astar算法的栅格地图目标最短路径搜索算法MATLAB仿真,带GUI界面
    1.算法描述       Astar算法是一种图形搜索算法,常用于寻路。它是个以广度优先搜索为基础,集Dijkstra算法与最佳优先(bestfit)算法特点于一身的一种算法。它通过......