T1077 多源最短路 codevs
2024-10-14 02:45:38
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 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 <algorithm>
#include <iostream>
#include <cstdio> using namespace std; int n,m,x,y;
int dis[][]; void Flyod(int x,int y)
{
for(int k=;k<=n;k++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j]=dis[i][k]+dis[k][j];
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&dis[i][j]);
cin>>m;
while(m--)
{
scanf("%d%d",&x,&y);
Flyod(x,y);
printf("%d\n",dis[x][y]);
} return ;
}
最新文章
- jQuery常用插件
- 【前端】CommonJS的模块加载机制
- Node Server管理
- sql条件中比较性能优化
- MyEclipse JCO tomcat 提示查找不到sapjco3.dll
- c# winfrom应用程序关闭任务管理器中的进程
- HDU 1025-Constructing Roads In JGShining&#39;s Kingdom(最长不降子序列,线段树优化)
- Qt... configure: error: Qt (>;= Qt 2.2.2) (headers…
- 不建议使用NSUserDefault存储大量数据
- Java JDBC连接SQL Server2005错误:通过port 1433 连接到主机 localhost 的 TCP/IP 连接失败
- 【转】centOS上安装redis+phpredis2.2.4扩展
- 【javascript】详解javascript闭包 — 大家准备好瓜子,我要开始讲故事啦~~
- SQL Server锁类型
- 在Storyboard中为UITableView添加Header和Footer
- 2017年php面试题汇总
- cocos creator主程入门教程(一)—— 初识creator
- GCC的__attribute__ ((constructor))和__attribute__ ((destructor))
- Redis中Pipeline的使用
- CSS编码规则
- Linux下找不到动态链接库;
热门文章
- apache 报413
- 【树状数组 思维题】luoguP3616 富金森林公园
- virtualenvwrapper.sh报错: There was a problem running the initialization hooks.解决
- (31)zabbix Aggregate checks聚合检测
- docker:安装redis
- ASP.NET使用Memcached高缓存实例的初级介绍
- 基于链式链表的栈链式存储的C风格实现
- final,buaa_oo conclusion
- Ubuntu14.04使用root登陆帐户
- Windows phone UI虚拟化和数据虚拟化(二)