poj1603(Flody算法)

news/2024/7/5 9:05:59

题意:题目确定只有20个国家,之间存在边界的话,距离设置为1。前面的19行,首先第i(1-19)行给出一个x,代表x后面跟的国家数,表示第i行和后面的国家之间存在边界,设置为1.第20行给出表示可能征服的起始国和结束国(也就是国家A和国家B之间的最短距离)。
使用Flody算法:
核心算法:

	for(int k=1;k<=20;k++){for(int i=1;i<=20;i++){for(int j=1;j<=20;j++){e[i][j]=min(e[i][k]+e[k][j],e[i][j]);}}}
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<iomanip>
#include<vector>
using namespace std;
const int maxx=22;
const int inf=0x3f3f3f3f;
int e[maxx][maxx];int m;
vector<int>vec[maxx];
void init(){for(int i=0;i<=maxx;i++){for(int j=0;j<=maxx;j++){if(i==j){e[i][j]=0;}else{e[i][j]=inf;}}}
}
void Flody(){for(int k=1;k<=20;k++){for(int i=1;i<=20;i++){for(int j=1;j<=20;j++){e[i][j]=min(e[i][k]+e[k][j],e[i][j]);}}}
}
int main(){int count=1;int n;while(scanf("%d",&n)!=EOF){init();for(int j=1;j<=n;j++){int x;cin>>x;e[1][x]=e[x][1]=1;}int t;for(int i=2;i<=19;i++){cin>>t;for(int j=1;j<=t;j++){int x;cin>>x;e[i][x]=e[x][i]=1;}}Flody();cin>>m;cout<<"Test Set #"<<count++<<endl;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;cout<<a<<" to "<<b<<": "<<e[a][b]<<endl;}cout<<endl;} return 0;
}

http://lihuaxi.xjx100.cn/news/285783.html

相关文章

log包在Golang语言的标准库中是怎么使用的?

Golang 语言的标准库中提供了一个简单的 log 日志包&#xff0c;它不仅提供了很多函数&#xff0c;还定义了一个包含很多方法的类型 Logger。但是它也有缺点&#xff0c;比如不支持区分日志级别&#xff0c;不支持日志文件切割等。 01、介绍 Golang 语言的标准库中提供了一个简…

DT时代下[个推3.0]遵循的四个法则

DT(Data Technology)&#xff0c;是以服务大众、激发生产力为主的技术。从IT时代走向DT时代&#xff0c;我们要思考如何用互联网技术、理念、思想去与传统行业进行交融和共同发展。 1.数据是决策的基本依据数亿客户端情况下&#xff0c;如何迅速定位&#xff1f;譬如&#xff1…

全栈AI工程师指南,DIY一个识别手写数字的web应用

作者 | shadow chi本文经授权转载自 无界社区mixlab&#xff08;ID&#xff1a;mix-lab&#xff09;网上大量教程都是教如何训练模型&#xff0c;往往我们只学会了训练模型&#xff0c;而实际应用的环节是缺失的。def AIFullstack&#xff08; &#xff09;&#xff1a;本文从「…

三国时期,假如曹操是一名程序员,历史会发生什么?--文末送书

点击上方[视学算法]→右上角[...]→[设为星标⭐]“东汉网络科技有限公司&#xff0c;本来是一家名扬四海的家族企业&#xff0c;可由于近几年来&#xff0c;越来越多的亲戚&#xff0c;在公司担任重要岗位&#xff0c;真正的人才越来越少&#xff0c;东汉网络开始走向了衰落。身…

HDU2199(二分算法)

题意&#xff1a;求解x在0到100之间是否存在唯一的解&#xff0c;使8x^ 47x^ 32x^23x6Y。 不存在解的情况是: Y<8f1(0)7f2(0)2f3(0)3f4(0)6或者 Y>8f1(100)7f2(100)2f3(100)3f4(100)6; 思路&#xff1a;采用二分的思想&#xff0c;当出现(right-left)>1e-8&#xff0c…

哈尔滨理工大学软件与微电子学院程序设计竞赛 题解

DEF题比较难一些&#xff0c;目前本菜鸡能力有限。 文章目录A-RaceB-Min ValueC-CoronavirusG-OXRH-MazeI-PrimeJ-CompareK-WalkL-Defeat the monsterA-Race 题解&#xff1a; 我们可以看到数据量并不是很大&#xff0c;所以我们可以选择一秒钟一秒钟来对这个比赛进行分析 在每…

来看看如何在 C# 中使用反射

C# 中的 反射 常用于在程序的运行时获取 类型 的元数据&#xff0c;可获取的信息包括已加载到进程中的 程序集 和 类型 信息&#xff0c;它和 C 中的 RTTI(Runtime Type Information) 的作用是差不多的。 C# 中的 反射 常用于在程序的运行时获取 类型 的元数据&#xff0c;可获…

我生于1997,我骄傲了吗?

本文经授权转载自公众号“图图是道”&#xff08;TTSD-TTSD&#xff09;1997&#xff0c;回归那年我出生在香港一户普普通通的家庭里爸爸给我起名嘉运他说既为了欢庆回归也为了庆祝度过金融风暴我小时候特别爱去海洋公园因为那有“安安”和“佳佳”妈妈说大熊猫是我们的国宝200…