[洛谷]P1529 [USACO2.4] 回家 Bessie Come Home

这篇具有很好参考价值的文章主要介绍了[洛谷]P1529 [USACO2.4] 回家 Bessie Come Home。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

最多52(a-z,A-Z)个点,所用有请floyd!!!

代码看一遍就很好理解做法啦


#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
string s1,s2;
int dist[60][60],d,p,ans=inf;
char ansc;
int getnum(char c){
	if(c>='a'&&c<='z')return c-'a'+26;
	else return c-'A';
}
void floyd(){
		for(int k=0;k<60;k++)
		for(int i=0;i<60;i++)
		for(int j=0;j<60;j++)
		dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
void init(){
	for(int i=0;i<60;i++)
	for(int j=0;j<60;j++)
	dist[i][j]=inf-1;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	init();

	cin>>p;
	while(p--){
		cin>>s1>>s2>>d;
		int x= getnum(s1[0]);
		int y=getnum(s2[0]);
		dist[x][y]=min(dist[x][y],d);
		dist[y][x]=min(dist[y][x],d);
	}
   floyd();

	for(int i=0;i<25;i++){
    	if(dist[i][25]<=ans){
		ans=dist[i][25];ansc=i+'A';
	}
}
	cout<<ansc<<" "<<ans<<"\n";
	return 0;
}

over~文章来源地址https://www.toymoban.com/news/detail-553742.html

到了这里,关于[洛谷]P1529 [USACO2.4] 回家 Bessie Come Home的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 信息学奥赛一本通 1375:骑马修栅栏(fence) | 洛谷 P2731 [USACO3.3]骑马修栅栏 Riding the Fences

    ybt 1375:骑马修栅栏(fence) 洛谷 P2731 [USACO3.3]骑马修栅栏 Riding the Fences 1. 图论:欧拉回路 欧拉回路存在的条件:图中所有顶点的度都是偶数 欧拉路径存在的条件:图中只有两个度为奇数的顶点。而且这两个顶点是欧拉路径的起点与终点。 求解欧拉回路使用Hierholzer算法 复杂度

    2024年02月08日
    浏览(40)
  • 洛谷题单 -- 图论的简单入门

    图的存储 - 洛谷 这一题要考察图的存储方式 , 一般可以使用邻接矩阵 或 邻接表来存储 图的结点 和1 边的信息 ,详情请看代码 :  【深基18.例3】查找文献 - 洛谷 这题考察有向图的 dfs 和 bfs ,详情请看代码,如果用邻接矩阵的话一定会mle,只能够使用邻接表,我这里采用的是用

    2024年04月13日
    浏览(44)
  • HOJ 系统常用功能介绍 部署快速入门 c++ python java编程语言在线自动评测 信息奥赛一本通 USACO GESP 洛谷 蓝桥 CSP NOIP题库

    技术支持微  makytony   终身更新维护 功能类似洛谷和信息奥赛一本通,支持CSP复赛中的freopen文件输入输出方式提交,模拟真实考试环境,防止出现 本地  AC 比赛  WA  PA TLE  爆零 的惨剧。 组织比赛作业,创建题目、查看用户提交代码、下载评测数据等都没限制。 约  328

    2024年02月13日
    浏览(41)
  • 【图论经典题目讲解】洛谷 P5304 旅行者

    D e s c r i p t i o n mathrm{Description} Description 给定一个 n n n 个点, m m m 条边的有向图,求解 k k k 个点两两间最短路长度的最小值。 S o l u t i o n mathrm{Solution} Solution 对于 k k k 个点,可以考虑二进制分组优化,即对于每一位为 1 1 1 的点放入 1 1 1 组(设为 A A A 组),为 0 0 0 的点

    2024年02月19日
    浏览(43)
  • 【图论经典题目讲解】洛谷 P2371 墨墨的等式

    D e s c r i p t i o n mathrm{Description} Description 求解有多少个 b ∈ [ l , r ] bin [l,r] b ∈ [ l , r ] 满足 ∑ i = 1 n a i x i = b sumlimits_{i=1}^n a_ix_i=b i = 1 ∑ n ​ a i ​ x i ​ = b 存在非负整数解( x i x_i x i ​ 为变量, a a a 数组给定)。 S o l u t i o n mathrm{Solution} Solution b b b 一定可以表示为

    2024年02月20日
    浏览(36)
  • 【图论经典题目讲解】洛谷 P2149 Elaxia的路线

    D e s c r i p t i o n mathrm{Description} Description 给定 n n n 个点, m m m 条边的无向图,求 2 2 2 个点对间最短路的最长公共路径 S o l u t i o n mathrm{Solution} Solution 最短路有可能不唯一,所以公共路径的长度就有可能不同。 将 2 2 2 条最短路都会经过的边(包括同向和异向)记录出来,

    2024年02月20日
    浏览(45)
  • HOJ 系统常用功能介绍 OJ部署快速入门 c++ python 编程语言在线自动评测判题 信息奥赛一本通 USACO GESP 洛谷 蓝桥 CSP NOIP 蓝桥等考题库

    技术支持微  makytony   终身更新维护 功能类似洛谷和信息奥赛一本通,支持CSP复赛中的freopen文件输入输出方式提交,模拟真实考试环境,防止出现 本地  AC 比赛  WA  PA TLE  爆零 的惨剧。 组织比赛作业,创建题目、查看用户提交代码、下载评测数据等都没限制。 约  328

    2024年02月07日
    浏览(53)
  • 洛谷题单【算法1-3】暴力枚举 P1157

            最近有很多自己想做的事情,但猛地发现自己似乎并没有将课内的课程知识学好,个人规划与学习安排之间似乎出现了不可忽视的冲突,于是上一周自己在无所事事中迷茫地摆了一周。打算从这周开始改变,就从每天坚持发帖子记录自己做题经验开始吧。 题目:

    2024年04月17日
    浏览(48)
  • 洛谷题单算法1-1模拟与高精度

    发文章只是为了督促自己做题,双非大二刚转科班的菜菜一枚,代码仅供参考,不足之处望理解。         这题太恶心了,看完题解发现三种情况没有考虑,后来给补上了,我的 if-else 思路可能写的不太好,但是能过         注意结构体在函数中的传参(下学期c语言II要好

    2024年02月19日
    浏览(44)
  • 洛谷题单--算法[2-1] 前缀和、差分与离散化

    目录 0.铺垫学习:p1115最大子段和--前缀和+贪心+DP 1.p1719最大加权矩形--前缀和+贪心+DP+矩阵压缩 原题链接: P1115 最大子段和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 原题: 题目描述 给出一个长度为 n 的序列 a,选出其中连续且非空的一段使得这段和最大。 输入格式 第

    2024年02月22日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包