第十四届蓝桥杯集训——练习解题阶段(无序阶段)-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个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
