codevs—— 1077 多源最短路
2024-10-07 11:36:22
题目描述 Description
已知n个点(n<=100),给你n*n的方阵,a[i,j]表示从第i个点到第j个点的直接距离。
现在有Q个询问,每个询问两个正整数,a和b,让你求a到b之间的最短路程。
满足a[i,j]=a[j,i];
输入描述 Input Description
第一行一个正整数n,接下来n行每行n个正整数,满足a[i,i]=0,再一行一个Q,接下来Q行,每行两个正整数a和b。
输出描述 Output Description
一共Q行,每行一个整数。
样例输入 Sample Input
3
0 1 1
1 0 3
1 3 0
1
2 3
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
n<=100,Q可能非常大。g[i][j]均>=0
请使用flyod算法
使用C/C++的同学请注意:由于输入数据较大,使用cin和cout会导致程序超时。请使用scanf与printf进行输入和输出。
活跃一下气氛、、、、
代码:
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define N 200 using namespace std; double k,b; int n,m,x,y,dis[N][N]; int read() { ,f=; char ch=getchar(); ; ch=getchar();} +ch-'; ch=getchar();} return x*f; } int main() { n=read(); ;i<=n;i++) ;j<=n;j++) x=read(),dis[i][j]=x; ;k<=n;k++) ;i<=n;i++) ;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); m=read(); ;i<=m;i++) { x=read(),y=read(); printf("%d\n",dis[x][y]); } }
最新文章
- 2 column数据构成主键的表转化为1 column为主键的表
- phpRedis安装、配置及简单使用
- 情人节那点事,Power BI告诉你
- Java中的经典算法之选择排序(SelectionSort)
- Flex利用titleIcon属性给Panel容器标题部添加一个ICON图标
- asp.net上传Excel文件到服务端进行读取
- 在 IIS 上创建 FTP 站点
- ASP.NET之AdRotator实现淘宝浏览页面的商品随机推荐功能
- linux下处理excel里copy的某列的字符串,去除行末空格并添加特殊字段
- kafka的高可用和一致性探究
- yii gridview 时间段筛选(一个输入框,自动提交,高清大图)
- android下载管理、理财、浏览器、商品筛选、录音源码等
- linux php7.2安装扩展memcached
- Docker+Jenkins+Maven+SVN搭建持续集成环境
- 通过这些示例快速学习Java lambda语法
- Java线程状态及 wait、sleep、join、interrupt、yield等的区别
- Hibernate: Implicit &; Explicit Polymorphism
- 03-树2 List Leaves (25 分)
- php初学习
- final 内部类 static
热门文章
- CSMA/CA协议
- HDU 5514 欧拉函数应用
- Android Studio Activity Intent 闪退崩溃 Toolbar
- java web 学习笔记 - Java Bean
- Filesystem Hierarchy Standard (Unix, Linux etc)
- sqlalchemy.exc.InvalidRequestError: Entity &#39;<;class &#39;model.TestCase&#39;>;&#39; has no property &#39;project&#39;
- gitlab恢复、迁移
- 【转载】jxl的使用总结(java操作excel)
- Linux kernel memory-faq.txt
- 使用Java中Calendar类测试当前年月日