Acwing.1375 奶牛回家(最短路朴素dijkstra)

2024-04-13 19:20

本文主要是介绍Acwing.1375 奶牛回家(最短路朴素dijkstra),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

晚餐时间马上就到了,奶牛们还在各自的牧场中悠闲的散着步。

当农夫约翰摇动铃铛,这些牛就要赶回牛棚去吃晚餐。

在吃晚餐之前,所有奶牛都在自己的牧场之中,有些牧场中可能没有奶牛。

每个牧场都通过一条条道路连接到一个或多个其他牧场(可能包括其自身)。

有时,两个(可能是相同的)牧场通过一条以上的道路相连。

至少存在一个牧场与牛棚通过一条道路直接相连。

所有奶牛都能够成功的从自己的牧场沿道路返回牛棚。

聪明的奶牛们总会选择最短的路径回到牛棚之中。

每条道路都是可以双向行走的,奶牛的行走速度也都一样。

我们用 a∼z 和 A∼Y 来标记所有的牧场。

所有用大写字母标记的牧场中都存在一头奶牛,所有用小写字母标记的牧场中都不存在奶牛。

牛棚的标记为 Z ,这里最初是没有奶牛的。

现在你需要确定,哪一头奶牛能够最快到达牛棚,输出它最初所在的牧场的标记,并输出它走过的路径的长度。

注意,同一字母大小写标记的两个牧场(例如,牧场 A 和牧场 a )是两个完全不同的牧场。

输入格式

第一行包含整数 P ,表示连接牧场以及牛棚的道路的条数。

接下来 P 行,每行包含两个字母以及一个整数,表示被一条道路连接的两个牧场的标记,以及这条道路的长度。

输出格式

输出一个字母和一个整数,表示最快回到牛棚的牛最初所在的牧场的标记以及它走过的路径的长度。

数据保证最快回到牛棚的牛只有一头。

数据范围

1≤P≤10000 , 所有道路长度均不超过 1000 。

  • 输入样例:
5
A d 6
B d 3
C e 9
d Z 8
e Z 3
  • 输出样例:
B 11

题解

import java.io.*;
import java.util.Arrays;/*** @author akuya* @create 2024-04-13-12:29*/
public class CowGoHome {static int N=60;static int n=52,m;static int g[][]=new int[N][N];static int dist[]=new int[N];static boolean st[]=new boolean[N];public static void main(String[] args) throws IOException {BufferedReader br=new BufferedReader(new InputStreamReader(System.in));PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));for(int i=0;i<N;i++){Arrays.fill(g[i],0x3f3f3f);}m=Integer.parseInt(br.readLine());while(m--!=0){String s[]=br.readLine().split(" ");char a=s[0].charAt(0);char b=s[1].charAt(0);int r=Integer.parseInt(s[2]);int A=get(a);int B=get(b);g[A][B]=g[B][A]=Math.min(g[A][B],r);}Dijkstra();int res=1;for(int i=2;i<=25;i++)if(dist[i]<dist[res])res=i;pw.println((char)(res-1+'A')+" "+dist[res]);br.close();pw.flush();pw.close();}public static int get(char c){if(c<='Z'){return c-'A'+1;}else return c-'a'+27;}public static void Dijkstra(){Arrays.fill(dist,0x3f3f3f);dist[26]=0;for(int i=0;i<n-1;i++){int t=-1;for(int j=1;j<=n;j++){if(!st[j]&&(t==-1||dist[j]<dist[t]))t=j;}st[t]=true;for(int j=1;j<=n;j++)dist[j]=Math.min(dist[j],dist[t]+g[t][j]);}}}

思路

本题为经典的单源最短路问题,因为可以从终点往其他节点遍历。然后是如何选择的问题,最短路选择什么方法。具体选择方法如图所示。这道题优先选择朴素dijstra算法,背诵模板使用即可。
在这里插入图片描述

这篇关于Acwing.1375 奶牛回家(最短路朴素dijkstra)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1502 MPI Maelstrom(单源最短路dijkstra)

题目真是长得头疼,好多生词,给跪。 没啥好说的,英语大水逼。 借助字典尝试翻译了一下,水逼直译求不喷 Description: BIT他们的超级计算机最近交货了。(定语秀了一堆词汇那就省略吧再见) Valentine McKee的研究顾问Jack Swigert,要她来测试一下这个系统。 Valentine告诉Swigert:“因为阿波罗是一个分布式共享内存的机器,所以它的内存访问

uva 10801(乘电梯dijkstra)

题意: 给几个电梯,电梯0 ~ n-1分别可以到达很多层楼。 换乘电梯需要60s时间。 问从0层到target层最小的时间。 解析: 将进入第0层的电梯60s也算上,最后减。 坑点是如果target为0输出0。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algori

poj 3159 (spfa差分约束最短路) poj 1201

poj 3159: 题意: 每次给出b比a多不多于c个糖果,求n最多比1多多少个糖果。 解析: 差分约束。 这个博客讲差分约束讲的比较好: http://www.cnblogs.com/void/archive/2011/08/26/2153928.html 套个spfa。 代码: #include <iostream>#include <cstdio>#i

hdu 3790 (单源最短路dijkstra)

题意: 每条边都有长度d 和花费p,给你起点s 终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 解析: 考察对dijkstra的理解。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin

poj 3255 次短路(第k短路) A* + spfa 或 dijkstra

题意: 给一张无向图,求从1到n的次短路。 解析: A* + spfa 或者 dijkstra。 详解见上一题:http://blog.csdn.net/u013508213/article/details/46400189 本题,spfa中,stack超时,queue的效率最高,priority_queue次之。 代码: #include <iostream>#i

poj 2449 第k短路 A* + spfa

poj 2449: 题意: 给一张有向图,求第k短路。 解析: A* + spfa。 一下转自:http://blog.csdn.net/mbxc816/article/details/7197228 “描述一下怎样用启发式搜索来解决K短路。 首先我们知道A*的基础公式:f(x)=g(x)+h(x);对h(x)进行设计,根据定义h(x)为当前的x点到目标点t所需要的实际距

poj 3259 最短路负环

John的农场里N块地,M条路连接两块地,W个虫洞,虫洞是一条单向路,会在你离开之前把你传送到目的地,就是当你过去的时候时间会倒退Ts。我们的任务是知道会不会在从某块地出发后又回来,看到了离开之前的自己。简化下,就是看图中有没有负权环。有的话就是可以,没有的话就是不可以了。 import java.io.BufferedReader;import java.io.InputStream;

POJ1724最短路

n个点,拥有总的价值money m条边(u,v,len ,cost),长度len,代价cost 求不超过money的代价条件下最短路。 public class Main {public static void main(String[] args) {new Task().solve();}}class Task {InputReader in = new InputReader