刷题记录-2最短路径

简介: 刷题记录-2最短路径

考点: 图论-最短路-Dijkstra






解题:

c++


#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const long long inf = 0x3f3f3f3f3f3f3f3fLL;
const int num = 3e5+2;
struct edge
{
    int from,to;
    long long w;
    edge(int a,int b,long long c)
    {
        from = a;
        to = b;
        w = c;
    }
};
vector<edge> e[num];
struct s_node
{
    int id;
    long long n_dis;
    s_node(int b,long long c)
    {
        id = b;
        n_dis = c;
    }
    bool operator < (const s_node a) const
    {
        return n_dis > a.n_dis;
    }
};
int n,m;
long long dis[num];
void dijstra()
{
    int s = 1;
    bool done[num];
    for(int i = 1;i <= n;i++)
    {
        dis[i] = inf;
        done[i] = false;
    }
    dis[s] = 0;
    priority_queue <s_node> Q;
    Q.push(s_node(s,dis[s]));
    while(!Q.empty())
    {
        s_node u = Q.top();
        Q.pop();
        if(done[u.id]) continue;
        done[u.id] = true;
        for(int i = 0;i < e[u.id].size();i++)
        {
            edge y = e[u.id][i];
            if(done[y.to]) continue;
            if(dis[y.to] > y.w +u.n_dis)
            {
                dis[y.to] = y.w + u.n_dis;
                Q.push(s_node(y.to,dis[y.to]));
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++) e[i].clear();
    while(m--)
    {
        int u,v,w;
        cin >> u >> v >> w;
        e[u].push_back(edge(u,v,w));
    }
    dijstra();
    for(int i = 1;i <= n;i++)
    {
        if(dis[i] >= inf) cout << "-1" << " ";
        else cout << dis[i] << " ";
    }
    return 0;
}


python


import heapq
import sys
n,m=map(int,input().split())
distance=[[] for i in range(n+1)]
for i in range(m):
  u,v,w=map(int,input().split())
  distance[u].append((v,w))
dp=[sys.maxsize]*(n+1)
q=[]
heapq.heappush(q,(0,1))
dp[1]=0
def dijkstra():
  visit=[0 for i in range(n+1)]
  while q:
    v=heapq.heappop(q)[1]
    if visit[v]==1:
      continue
    visit[v]=1
    for a,b in distance[v]:
      if visit[a]==1:
        continue
      dp[a]=min(dp[a],dp[v]+b)
      heapq.heappush(q,(dp[a],a))
dijkstra()
print(0,end=" ")
for i in range(2,n+1):
  if dp[i]==sys.maxsize:
    print(-1,end=" ")
  else:
    print(dp[i],end=" ")


看了一下别的大佬的解题思路,很厉害的


# 请在此输入您的代码
import math
import heapq
def djs(s):
    done = [0 for _ in range(n + 1)]  # bool矩阵
    hp = []
    dis[s] = 0
    heapq.heappush(hp, (0, s))  
    while hp:
        t = heapq.heappop(hp)[1]  # 取出该节点
        if done[t]:
            continue
        done[t] = 1
        for i in range(len(g[t])):  # 找t的邻居节点和距离
            v, w = g[t][i]
            if done[v]:
                continue
            if dis[v] > dis[t] + w:
                dis[v] = dis[t] + w
                heapq.heappush(hp, (dis[v], v))
n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]  # 用邻接表来储存图
dis = [math.inf] * (n + 1)  
for i in range(m):
    u, v, w = map(int, input().split())
    g[u].append((v, w))  # 用邻接表来储存图
djs(1)
for i in range(1, n+1):
    if dis[i] >= math.inf:
        print(-1, end=' ')
    else:
        print(dis[i], end=' ')
目录
打赏
0
0
0
0
14
分享
相关文章
刷题记录:牛客-WY49数对 | 以数学分析来破解暴力搜索的时间复杂度问题 2023/1/11
这是一个关于编程题解的文章摘要,讨论了一道名为&quot;WY49 数对&quot;的问题。文章指出,暴力搜索的解决方案在大规模问题中效率低下,然后转向通过数学分析来寻找更优解。作者解释了如何根据除数和余数的关系,以及余数的周期性变化来计算满足条件的数对数量。通过将数对中的其中一个数(被模数x)按除数y划分区间,并分析每个区间的余数分布,得出一个公式来计算总数。最后,提供了两种不同的代码实现来展示这个思路,这些代码具有O(n)的时间复杂度和O(1)的空间复杂度。文章强调了理解数学方法在解决此类问题中的重要性,特别是对于优化算法性能的作用。
131 3
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
刷爆 LeetCode 周赛 337,位掩码/回溯/同余/分桶/动态规划·打家劫舍/贪心
上周末是 LeetCode 第 337 场周赛,你参加了吗?这场周赛第三题有点放水,如果按照题目的数据量来说最多算 Easy 题,但如果按照动态规划来做可以算 Hard 题。
137 0
[蓝桥杯][历届试题]九宫重排(BFS+哈希)
如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面。
231 1
[蓝桥杯][历届试题]九宫重排(BFS+哈希)
【刷题记录】46. 全排列
【刷题记录】46. 全排列
140 0
【刷题记录】46. 全排列
【刷题记录】1. 两数之和
【刷题记录】1. 两数之和
130 0
【刷题记录】1. 两数之和
【刷题记录】36. 有效的数独
【刷题记录】36. 有效的数独
174 0
【刷题记录】36. 有效的数独
【刷题记录】15.三数之和
【刷题记录】15.三数之和
169 0
【刷题记录】15.三数之和
剑指offer 二叉树专题 刷题记录(1)
剑指offer 二叉树专题 刷题记录(1)
131 0
剑指offer 二叉树专题 刷题记录(1)