<USACO09DEC>过路费Cow Toll Pathsの思路
2024-08-30 00:01:01
啊好气 在洛谷上A了之后 隔壁jzoj总wa
迷茫了很久.发现那题要文件输入输出
生气
肥肠不爽
Description
- 跟所有人一样,农夫约翰以着宁教我负天下牛,休叫天下牛负我的伟大精神,日日夜夜苦思生财之道。为了发财,他设置了一系列的规章制度,使得任何一只奶牛在农场中的道路行走,都要向农夫约翰上交过路费。
农场中由N(1 <= N <= 250)片草地(标号为1到N),并且有M(1 <= M <= 10000)条双向道路连接草地A_j和B_j(1 <= A_j <= N; 1 <= B_j <= N)。奶牛们从任意一片草地出发可以抵达任意一片的草地。FJ已经在连接A_j和B_j的双向道路上设置一个过路费L_j(1 <= L_j <= 100,000)。
可能有多条道路连接相同的两片草地,但是不存在一条道路连接一片草地和这片草地本身。最值得庆幸的是,奶牛从任意一篇草地出发,经过一系列的路径,总是可以抵达其它的任意一片草地。
除了贪得无厌,叫兽都不知道该说什么好。FJ竟然在每片草地上面也设置了一个过路费C_i(1 <= C_i <= 100000)。从一片草地到另外一片草地的费用,是经过的所有道路的过路费之和,加上经过的所有的草地(包括起点和终点)的过路费的最大值。
任劳任怨的牛们希望去调查一下她们应该选择那一条路径。她们要你写一个程序,接受K(1<= K <= 10,000)个问题并且输出每个询问对应的最小花费。第i个问题包含两个数字s_i和t_i(1 <= s_i <= N; 1 <= t_i <= N; s_i != t_i),表示起点和终点的草地。
考虑下面这个包含5片草地的样例图像:
从草地1到草地3的道路的“边过路费”为3,草地2的“点过路费”为5。
要从草地1走到草地4,可以从草地1走到草地3再走到草地5最后抵达草地4。如果这么走的话,需要的“边过路费”为2+1+1=4,需要的点过路费为4(草地5的点过路费最大),所以总的花费为4+4=8。
而从草地2到草地3的最佳路径是从草地2出发,抵达草地5,最后到达草地3。这么走的话,边过路费为3+1=4,点过路费为5,总花费为4+5=9。Input
- 第1行: 三个空格隔开的整数: N, M和K
- 第2到第N+1行: 第i+1行包含一个单独的整数: C_i
- 第N+2到第N+M+1行: 第j+N+1行包含3个由空格隔开的整数: A_j, B_j和L_j
- 第N+M+2倒第N+M+K+1行: 第i+N+M+1行表示第i个问题,包含两个由空格隔开的整数s_i和t_i
Output
第1到第K行: 第i行包含一个单独的整数,表示从s_i到t_i的最小花费。
Sample Input
- 5 7 2
2
5
3
3
4
1 2 3
1 3 2
2 5 3
5 3 1
5 4 1
2 4 3
3 4 4
1 4
2 3
Sample Output
8
9
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n[][],cc[][],w[];
int N,m,k,u,v,l,s,t;
struct node{
int id,w;
}c[];
void floyd()
{
int p,o,i,j;
for(i=;i<=N;i++)
cc[i][i]=c[i].w;
for(p=;p<=N;p++)
{
o=c[p].id;
for(i=;i<=N;i++)
for(j=;j<=N;j++)
{
if(n[i][j]>n[i][o]+n[o][j])n[i][j]=n[j][i]=n[i][o]+n[o][j];//单纯的多源最短路
if(cc[i][j]>n[i][j]+max(c[p].w,max(w[i],w[j])))cc[i][j]=cc[j][i]=n[i][j]+max(c[p].w,max(w[i],w[j]));//带上点权.!
}
}
}
bool cmp(node a,node b){return a.w<b.w;}
int main()
{
int i,j;
//freopen("toll.in","r",stdin);
//freopen("toll.out","w",stdout);
scanf("%d%d%d",&N,&m,&k);
memset(n,,sizeof(n));
memset(cc,,sizeof(cc));
for(i=;i<=N;i++)n[i][i]=;
for(i=;i<=N;i++)scanf("%d",&c[i].w),c[i].id=i,w[i]=c[i].w;
sort(c+,c+N+,cmp);//排序.! for(i=;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&l);
n[v][u]=n[u][v]=min(n[u][v],l);
}
floyd();
for(i=;i<=k;i++)
{
scanf("%d%d",&s,&t);
printf("%d\n",cc[s][t]);
}
return ;
}
点击查看丑陋の代码&注释
最新文章
- Hawk 数据抓取工具 使用说明(二)
- 网络基础知识之 Ping
- php 获取远程图片保存到本地
- BZOJ3282——Tree
- c#开发Mongo笔记第八篇
- 无法加载程序集,因为该程序集包含EdmSchemaAttribute,并按名称加载结束类型。不允许同时按名称和特性进行加载
- 让CALayer的shadowPath跟随bounds一起做动画改变-b
- Cadence原理图与Allegro交互
- asp.net 时间比较,常用于在某段时间进行操作
- Flash,EEPROM差别
- window.onerror 应用实例
- PrintService类打印
- SQL 性能分析
- js的event事件对象汇总
- hdu 1542 线段树+扫描线 学习
- Win7自带功能,刻录光盘遇到的问题
- Linux netstat命令介绍
- [UE4]IES光源概述文件
- 3.控制hive map reduce个数
- UE查找和替换技巧实例
热门文章
- 01 语言基础+高级:1-8 File类与IO流_day10【缓冲流、转换流、序列化流】
- Ubuntu---gedit 打开windows 下 .txt 文件乱码的解决方法
- .jar文件不能解析、识别
- Java之同步代码块处理继承Thread类的线程安全问题
- Window RabbitMq安装
- Python笔记_第一篇_面向过程_第一部分_5.Python数据类型之元组类型(tuple)
- @Retention注解 @Documented 注解 @Inherited 注解
- split - 拆分文件
- LGOJ1861 星之器
- svn文件冲突,树冲突详解