2673 最短路径

2024-03-04 15:58
文章标签 路径 最短 2673

本文主要是介绍2673 最短路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接
朴素Dijkstra算法
包含重边和自环

#include <iostream>
#include <vector>
#include <algorithm> 
#include <cmath>
#include <cstring>
using namespace std;
const int N = 505;
const int INF = 0x3f3f3f3f;
int G[N][N];
int n, m;
int d[N];
bool st[N];
void Dijkstra(int s){memset(d, 0x3f, sizeof d);d[s] = 0;for(int i = 0; i < n; i++){ //迭代n次 int u = -1;for(int j = 1; j <= n; j++)if(!st[j] && (u == -1 || d[u] > d[j])){u = j;}st[u] = true;for(int v = 1; v <= n; v++){d[v] = min(d[v], d[u] + G[u][v]);}}
}
int main(){cin>>n>>m;int u, v, w;memset(G, 0x3f,sizeof G);for(int i = 0; i < m; i++){cin>>u>>v>>w;G[u][v] = min(w, G[u][v]);G[v][u] = min(w, G[v][u]);}int st, ed;cin>>st>>ed;Dijkstra(st);cout<<d[ed]<<endl;return 0;
}

这篇关于2673 最短路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/773691

相关文章

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

【408DS算法题】039进阶-判断图中路径是否存在

Index 题目分析实现总结 题目 对于给定的图G,设计函数实现判断G中是否含有从start结点到stop结点的路径。 分析实现 对于图的路径的存在性判断,有两种做法:(本文的实现均基于邻接矩阵存储方式的图) 1.图的BFS BFS的思路相对比较直观——从起始结点出发进行层次遍历,遍历过程中遇到结点i就表示存在路径start->i,故只需判断每个结点i是否就是stop

Android Environment 获取的路径问题

1. 以获取 /System 路径为例 /*** Return root of the "system" partition holding the core Android OS.* Always present and mounted read-only.*/public static @NonNull File getRootDirectory() {return DIR_ANDR

图的最短路径算法——《啊哈!算法》

图的实现方式 邻接矩阵法 int[][] map;// 图的邻接矩阵存储法map = new int[5][5];map[0] = new int[] {0, 1, 2, 3, 4};map[1] = new int[] {1, 0, 2, 6, 4};map[2] = new int[] {2, 999, 0, 3, 999};map[3] = new int[] {3, 7

vcpkg子包路径批量获取

获取vcpkg 子包的路径,并拼接为set(CMAKE_PREFIX_PATH “拼接路径” ) import osdef find_directories_with_subdirs(root_dir):# 构建根目录下的 "packages" 文件夹路径root_packages_dir = os.path.join(root_dir, "packages")# 如果 "packages"

jmeter依赖jar包找不到类路径

这两天我在纠结这个问题,为啥我maven打包放在jmeter路径下后,jmeter的bean Shell 就是找不到这个类。纠结很久解开了。我记录下,留给后来的朋友。   Error invoking bsh method: eval Sourced file: inline evaluation of: ``import org.apache.jmeter.protocol.http.s

运行.bat文件,如何在Dos窗口里面得到该文件的路径

把java代码打包成.jar文件,编写一个.bat文件,执行该文件,编译.jar包;(.bat,.jar放在同一个文件夹下) 运行.bat文件,如何在Dos窗口里面得到该文件的路径,并运行.jar文件: echo 当前盘符:%~d0 echo 当前路径:%cd% echo 当前执行命令行:%0 echo 当前bat文件路径:%~dp0 echo 当前bat文件短路径:%~sdp0 nc

【uva】116-Unidirectional TSP(动态规划,路径问题)

一道很基础的动态规划,不过需要考虑路径(而且是最小字典序)。 转移方程很好写: d[i][j] = min(dp[i + 1][ j] ,dp[i + 1][j - 1] ,dp[i + 1][ j - 1]) + mat[j[i]; dp[i][j]代表走到第i列第行的时候距离最后一行的最短距离; 13991881 116 Unidirectional TSP Accepted C

力扣 797. 所有可能路径【DFS】

1. 题目 2. 代码 DFS , 直接见代码 class Solution {public:vector<int> path;vector<vector<int>> res; // 结果集void dfs(vector<vector<int>>& graph, int cur, int n){// 找出所有从节点 0 到节点 n-1 的路径// 下标从 0 开始的if (