HDU 1690 最短路
2024-09-06 02:50:44
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std; typedef __int64 ll;
#define inf 0x3f3f3f3f
//#define inf 0x7f7f7f7f7f7f7f7fLL
#define min(x,y) (x<y?x:y)
ll l1,l2,l3,l4,c1,c2,c3,c4;
int n,m;
ll x[];
ll dist[][]; void floyd(){
for(int k=;k<=n;k++){
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(dist[i][k]==inf||dist[k][j]==inf){
continue;
}
ll res=dist[i][k]+dist[k][j];
if(res<dist[i][j]){
dist[i][j]=res;
}
}
}
}
} int main(){
int T;
scanf("%d",&T);
for(int t=;t<=T;t++){
scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d",&l1,&l2,&l3,&l4,&c1,&c2,&c3,&c4);
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%I64d",&x[i]);
}
for(int i=;i<=n;i++){
for(int j=i+;j<=n;j++){
ll d=x[i]-x[j];
if(d<){
d*=-;
}
if(<d&&d<=l1){
dist[i][j]=dist[j][i]=c1;
}
else if(l1<d&&d<=l2){
dist[i][j]=dist[j][i]=c2;
}
else if(l2<d&&d<=l3){
dist[i][j]=dist[j][i]=c3;
}
else if(l3<d&&d<=l4){
dist[i][j]=dist[j][i]=c4;
}
else{
dist[i][j]=dist[j][i]=inf;
}
}
}
floyd();
printf("Case %d:\n",t);
for(int i=;i<m;i++){
int a,b;
scanf("%d%d",&a,&b);
if(dist[a][b]==inf){
printf("Station %d and station %d are not attainable.\n",a,b);
}
else{
printf("The minimum cost between station %d and station %d is %I64d.\n",a,b,dist[a][b]);
}
}
}
}
最新文章
- KSFramework配置表:扩展表格解析类型
- BZOJ4367 : [IOI2014]holiday假期
- <;[你在荒废时间的时候别人都在拼命!]>;
- PHP 设计模式 笔记与总结(9)数据对象映射模式
- ADB not responding. If you&#39;d like to retry, then please manually kill ";adb.exe"; and click &#39;Restart&#39;
- 处理SVN的提交代码冲突
- 管理Java垃圾回收的五个建议
- JVM performance profiling (有待整理)
- 章节2:SQL之多表连接
- 初识Python-web框架的这两天
- VIM 多行输入 数字递增 新方法 循环记录法
- C++malloc,calloc,realloc,free函数
- 用vue实现简单实时汇率计算功能
- CentOS7 离线安装gcc/pcre-devel/openssl-devel/zlib-devel
- 笔记整理--Linux平台MYSQL的C语言
- day12<;常见对象+>;
- redis咋么实现分布式锁,redis分布式锁的实现方式,redis做分布式锁 积极正义的少年
- Python之黏包的解决
- 13.git的简单使用
- 20165213 Exp4 恶意代码分析
热门文章
- window查看端口信息
- <;每日一题>;题目21:简单的python练习题(21-30)
- 如何使用Pig集成分词器来统计新闻词频?
- oracle中utl_file包读写文件操作实例学习
- HZOI20190908模拟40 队长快跑,影魔,抛硬币 题解
- HDU 6003 Problem Buyer
- [jeecms]获取父栏目下的子栏目名称
- com.microsoft.sqlserver.jdbc.SQLServerException: 将截断字符串或二进制数据。
- CentOS 6.8 Linux系统U盘制作启动项
- 浓缩版 《C和指针》基础篇(Chpt.1~Chpt.9)