第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-5 算法训练 最短路

简介: 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-5 算法训练 最短路

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-5 算法训练 最短路


前言

       最近的一些文章都可能会很碎,写到哪里是哪里,过一阵子会具体的整理一遍,这里其它的类型题先往后排一排,因为蓝桥最后考的也就是对题目逻辑的理解能力,也就是dp分析能力了,所以就主要目标定在这里,最近的题目会很散,很多,基本上都是网罗全网的一些dp练习题进行二次训练,准备比赛的学生底子薄的先不建议看啊,当然,脑子快的例外,可以直接跳过之前的一切直接来看即可,只需要你在高中的时候数学成绩还可以那就没啥问题,其实,dp就是规律总结,我们只需要推导出对应题目的数学规律就可以直接操作,可能是一维数组,也可能是二维数组,总体来看二维数组的较多,但是如果能降为的话建议降为,因为如果降为起来你看看时间复杂度就知道咋回事了,那么在这里祝大家能无序的各种看明白,争取能帮助到大家。


算法训练 最短路

资源限制

内存限制:256.0MB   C/C++时间限制:1.0s   Java时间限制:3.0s   Python时间限制:5.0s

问题描述

给定一个n个顶点,m条边的有向图(其中某些边权可能为负,但保证没有负环)。请你计算从1号点到其他点的最短路(顶点从1到n编号)。

输入格式

第一行两个整数n, m。

接下来的m行,每行有三个整数u, v, l,表示u到v有一条长度为l的边。

输出格式

共n-1行,第i行表示1号点到i+1号点的最短路。

样例输入

3 3

1 2 -1

2 3 -1

3 1 2

样例输出

-1

-2

数据规模与约定

对于10%的数据,n = 2,m = 2。

对于30%的数据,n <= 5,m <= 10。

对于100%的数据,1 <= n <= 20000,1 <= m <= 200000,-10000 <= l <= 10000,保证从任意顶点都能到达其他所有顶点。

题解,最短路径的问题相对来说我们就可以直接套搜索了,队列操作,我们可以选择广搜bfs。

C语言

#include<stdio.h>
int dis[20005],u[200005],v[200005],w[200005];
int main()
{
  int m,n,i,k,check;
  int inf=99999999;
  scanf("%d%d",&n,&m);
  for(i=1;i<=m;i++)
    scanf("%d%d%d",&u[i],&v[i],&w[i]);
  for(i=1;i<=n;i++)
    dis[i]=inf;
  dis[1]=0;
  for(k=1;k<=n-1;k++){
    check=0;
    for(i=1;i<=m;i++){
      if(dis[v[i]]>dis[u[i]]+w[i]){
        dis[v[i]]=dis[u[i]]+w[i];
        check=1;}
      }
    if(check==0)
      break;}
  for(i=2;i<=n;i++)
    printf("%d\n",dis[i]);
  return 0;
}

C++语言

#include<stdio.h>  
 #include<string.h>  
 #define inf 100000  
 struct In{  
     int e;  
     int w;  
     int next;  
 }map[200010];  
 int dis[20010],Q[20010];  
 int vis[20010],head[20010];  
 void SPFA(int n){  
     int i,j,front,rear,temp;  
     for(i=1;i<=n;i++){  
         dis[i]=inf;  
     }  
     dis[1]=0;vis[1]=1;  
     front=0;rear=1;  
     Q[front]=1;  
     while(front<rear){  
         temp=Q[front++];  
         vis[temp]=0;  
         j=head[temp];  
         while(j>0){  
             if(dis[map[j].e]>map[j].w+dis[temp]){  
                 dis[map[j].e]=map[j].w+dis[temp];  
                 if(!vis[map[j].e]){  
                     Q[rear++]=map[j].e;  
                     vis[map[j].e]=1;   
                 }  
             }  
             j=map[j].next;  
         }  
     }  
 }  
 int main(){  
     int n,m,i,j,a,b,val;  
     while(~scanf("%d%d",&n,&m)){  
         memset(Q,0,sizeof(Q));  
         memset(head,0,sizeof(head));  
         memset(vis,0,sizeof(vis));  
         for(i=1;i<=m;i++){  
             scanf("%d%d%d",&a,&b,&val);  
             map[i].e=b;  
             map[i].w=val;  
             map[i].next=head[a];  
             head[a]=i;  
         }  
         SPFA(n);  
         for(i=2;i<=n;i++){  
             printf("%d\n",dis[i]);  
         }  
     }  
     return 0;  
 }

Java语言

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
public class Main {
  static int leng[];
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    List<node> list[] = new ArrayList[n];// 存储路径
    for (int i = 0; i < n; i++)// 声明
    {
      list[i] = new ArrayList<node>();
    }
    leng = new int[n];
    boolean jud[] = new boolean[n];// 判断是否在队列内
    for (int i = 1; i < n; i++) {
      leng[i] = Integer.MAX_VALUE;
    } // 初始最长均为max
    for (int i = 0; i < m; i++) {
      int u = sc.nextInt();
      int v = sc.nextInt();
      int l = sc.nextInt();
      list[u - 1].add(new node(v - 1, l));
    }
    Queue<Integer> q1 = new ArrayDeque<Integer>();
    q1.add(0);// 第一个
    while (!q1.isEmpty()) {
      int x = q1.poll();
      jud[x] = false;
      for (int i = 0; i < list[x].size(); i++)// 遍历
      {
        int index = list[x].get(i).x;// x邻居该节点的编号
        int length = list[x].get(i).leng;// x到这个邻居的距离
        if (leng[index] > leng[x] + length) {
          leng[index] = leng[x] + length;
          if (!jud[index])// 队列中没有该点
          {
            q1.add(index);
            jud[index] = true;
          }
        }
      }
    }
    for (int i = 1; i < n; i++) {
      System.out.println(leng[i]);
    }
  }
  static class node {
    int x;
    int leng;
    public node(int x, int leng) {
      this.x = x;
      this.leng = leng;
    }
  }
}

Python语言

队列的广搜,代码看着不是很多,其实复杂度不低。

n,m=map(int,input().split())
g=[dict() for i in range(n+1)]
for i in range(m):
    u,v,l=map(int,input().split())
    g[u][v]=l
queue=[1]
visited=[True if i==1 else False for i in range(n+2)]
inf=1000000000
dist=[0 if i==1 else inf for i in range(n+2)]
while queue!=[]:
    rhs=queue.pop(0)
    visited[rhs]=False
    dicts=g[rhs]
    if dicts!={}:
        for key,value in dicts.items():
            if dist[key]>dist[rhs]+value:
                dist[key]=dist[rhs]+value
                if not visited[key]:
                    visited[key]=True
                    queue.append(key)
for i in range(2,n+1):
    print(dist[i])

总结

最短路问题在蓝桥杯中出现的频次还是非常高的,我们需要根据对应的题目做出搜索的选择,但是一般最短路都是广搜。

没有什么不付出就能拿到的结果,我们都是在负重前行,最终结果与自身先天的脑力有一定的关系,但是还是有很大一部分看自己后天的努力,其实从报名到比赛也就5个月左右,真正刷题的事件也就2个月,2个月回忆一下你真正的认真刷过题吗,如果你真的用尽所有的精力去努力了,那么我相信你最终的成绩一定会让你满意的,加油。


相关文章
|
4月前
|
存储 机器学习/深度学习 算法
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
42 3
|
2天前
|
算法 Java C++
【贪心算法】算法训练 ALGO-1003 礼物(C/C++)
【贪心算法】算法训练 ALGO-1003 礼物(C/C++)
【贪心算法】算法训练 ALGO-1003 礼物(C/C++)
|
2天前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
2天前
|
算法 C++
蓝桥 算法训练 共线(C++)
蓝桥 算法训练 共线(C++)
|
3月前
knn增强数据训练
【7月更文挑战第27天】
29 10
|
3月前
|
数据采集 编解码 人工智能
破解ChatGPT惊人耗电!DeepMind新算法训练提效13倍,能耗暴降10倍
【7月更文挑战第19天】DeepMind的JEST算法革新AI训练,提升效率13倍,节能10倍。通过联合数据批次选择,预训练指导及多分辨率训练,优化资源利用,降低能耗。实验显示性能提升,达到SOTA水平,但实施需大量资源,依赖优质参考模型。[论文链接](https://arxiv.org/pdf/2406.17711)
58 10
|
3月前
knn增强数据训练
【7月更文挑战第28天】
23 2
|
2月前
|
算法 搜索推荐
支付宝商业化广告算法问题之基于pretrain—>finetune范式的知识迁移中,finetune阶段全参数训练与部分参数训练的效果如何比较
支付宝商业化广告算法问题之基于pretrain—>finetune范式的知识迁移中,finetune阶段全参数训练与部分参数训练的效果如何比较
|
3月前
|
人工智能 边缘计算 算法
破解ChatGPT惊人耗电!DeepMind新算法训练提效13倍,能耗暴降10倍
【7月更文挑战第20天】DeepMind unveils Switch Transformer, revolutionizing AI energy consumption. This novel algorithm boosts training efficiency by 13x and slashes energy use by 10x compared to ChatGPT, marking a significant leap towards eco-friendly AI.
40 2
|
2月前
|
存储 算法
【C算法】编程初学者入门训练140道(1~20)
【C算法】编程初学者入门训练140道(1~20)