2017 Multi-University Training Contest - Team 4 hdu6071 Lazy Running
地址:http://acm.split.hdu.edu.cn/showproblem.php?pid=6071
题目:
Lazy Running
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 144 Accepted Submission(s): 62
There are 4 checkpoints in the campus, indexed as p1,p2,p3 and p4. Every time you pass a checkpoint, you should swipe your card, then the distance between this checkpoint and the last checkpoint you passed will be added to your total distance.
The system regards these 4 checkpoints as a circle. When you are at checkpoint pi, you can just run to pi−1 or pi+1(p1 is also next to p4). You can run more distance between two adjacent checkpoints, but only the distance saved at the system will be counted.
Checkpoint p2 is the nearest to the dormitory, Little Q always starts and ends running at this checkpoint. Please write a program to help Little Q find the shortest path whose total distance is not less than K.
In each test case, there are 5 integers K,d1,2,d2,3,d3,4,d4,1(1≤K≤1018,1≤d≤30000), denoting the required distance and the distance between every two adjacent checkpoints.
2000 600 650 535 380
The best path is 2-1-4-3-2.
#include <bits/stdc++.h> using namespace std; #define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-;
const double pi=acos(-1.0);
const int K=1e6+;
const int mod=1e9+; int n,d12,d23,d34,d41;;
LL d[][],dk,p;
vector<PII>mp[];
void spfa(void)
{
queue<pair<LL,LL>>q;
for(int i=;i<=;i++)
for(int j=;j<p;j++)
d[i][j]=2e18;
q.push(MP(2LL,0LL));
while(q.size())
{
LL u=q.front().first,w=q.front().second;
q.pop();
if(w>dk*)continue;
for(auto v:mp[u])
if(d[v.first][(w+v.second)%p]>w+v.second)
{
d[v.first][(w+v.second)%p]=w+v.second;
q.push(MP(v.first,w+v.second));
}
}
}
int main(void)
{
int t;cin>>t;
while(t--)
{
memset(mp,,sizeof mp);
scanf("%lld%d%d%d%d",&dk,&d12,&d23,&d34,&d41);
mp[].PB(MP(,d12)),mp[].PB(MP(,d41));
mp[].PB(MP(,d12)),mp[].PB(MP(,d23));
mp[].PB(MP(,d23)),mp[].PB(MP(,d34));
mp[].PB(MP(,d34)),mp[].PB(MP(,d41));
p=2LL*min(d12,d23);
spfa();
LL ans=2e18;
for(int i=;i<p;i++)
if(d[][i]>=dk)
ans=min(d[][i],ans);
else
ans=min((dk-d[][i]+p-)/p*p+d[][i],ans);
printf("%lld\n",ans);
}
return ;
}
最新文章
- 关于Function.prototype.bind
- 第二章 rabbitmq在mac上的安装
- ccpc-1008-HDU5839Special Tetrahedron-计算几何
- 正则匹配中文.PHP不兼容的问题
- [HDU 4585] Shaolin (map应用)
- 锋利的jquery-选择器
- 对Kalman(卡尔曼)滤波器的理解
- bootstropt-table 大量字段整体表单上传之时间处理
- IIS下自定义错误页面配置的两种方式(亲测可行)--IIS服务器
- Exp2 后门原理与实践 20164311
- Codeforces 830C Bamboo Partition 其他
- noip2016海港
- Linux命令:pwd
- 五花八门的CSS
- Linux 下载安装配置Redis完整步骤
- Go Revel - app.conf
- hdu2243 考研路茫茫——单词情结【AC自动机】【矩阵快速幂】
- pm2以windows服务运行
- ubuntu64位库
- Oracle 与Sql Server常用函数对比
热门文章
- 利用新浪云平台(SAE) 搭建 HUSTOJ 简易教程
- ios 从URL中截取所包含的参数,并且以字典的形式返回和参数字典转URL
- (转)有关thread线程
- MyEclipse------如何添加jspsmartupload.jar,用于文件上传
- Codeforces Round #296 (Div. 2) B. Error Correct System
- Makefile foreach(转)
- Myeclipse下使用Maven搭建spring boot项目
- 【BZOJ2956】模积和 分块
- 该死的Kafka,远程连接Kafka超时以及解决办法
- Java 使用阿里云短信的API接口