题解 P5037 【抓捕】
_虹_
2018-12-22 21:48:43
刚刚看到有大佬举报这题抄袭题解这事才想起这道题。
分享一个 ~~赛后十分钟写出来的~~ **诡异**的做法
init函数预处理出所有不互质的点对。
**任意房间都有走廊相连**，所以不需要连边，只要两点互质就存在一条边，边权=出发点点权。在这张图上跑dij+heap。
~~印象中t了。~~
记录ans=min(ans,result[y])，在relax的时候放弃所有result[v]>=ans的点u的relax，相当于是在最短路树上剪枝。
然后AC了。
效率不如出题人题解提到的relax点y时终止dij的方法，但是这道题上慢的不多，实测后5个点慢10ms多一点。
~~程序不吸氧总用时600ms上下。并不知道为什么会这么快。。。。不知道有没有大佬讲解一下。。。。~~
~~rank1 31ms / 2.78MB ，不知道大佬用了什么神仙算法。orz~~
```cpp
//#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const unsigned int INT_MAX=2147483647;
const int kmaxn=4500+5;
const int kmaxm=kmaxn<<4;
//////////////////////////////////////////////////////////////////////////////////
struct unit
{
int first;
int second;
unit():first(0),second(0){};
inline unit(const int& f,const int& s):first(f),second(s){};
const int inline operator<(const unit& u)const
{
return first>u.first;
}
};
class p_queue
{
unit heap[kmaxm];
int otail;
public:
p_queue():otail(0){};
unit inline top(){
pop_heap(&heap[0],&heap[otail]);
return heap[otail-1];
}
void inline pop(){--otail;
}
void inline push(const unit& v){
heap[otail++]=v;
push_heap(&heap[0],&heap[otail]);
}
const bool inline empty()const{return !otail;}
}q;
//priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
/////////////////////////////////////////////////////////////////////////////////
bool unable[kmaxn][kmaxn];
int result[kmaxn];//走到i点消耗的最小体力
int value[kmaxn];//从i点出发消耗掉的体力
bool hsh[kmaxn];
int otail=0;
int n;
int ans;
int x,y;
void inline relax(const int& p)
{
register int v=result[p]+value[p];
if(ans<=v)
return;
for(register int i=2;i<=n;++i)
{
if(!hsh[i]&&!unable[p][i]&&(result[i]<0||result[i]>v))
{
result[i]=v;
if(i==y)
ans=v;
else if(v<ans)
// q.push(make_pair(v,i));
q.push(unit(v,i));
//cout<<i<<" "<<p<<endl;
}
}
}
void inline shortest_path(const int& start)
{
ans=INT_MAX;
//q.push(make_pair(0,start));
q.push(unit(0,start));
result[start]=0;
int t=0;
while(!q.empty())
{
t=q.top().second;
q.pop();
if(!hsh[t])
{
relax(t);
hsh[t]=true;
}
}
}
/*void inline add_edge(const int& s,const int &d,const int &w)
{
if(s!=d)
map[s][d]=w;
}*/
inline int read(){
register int s=0,w=1;
register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int t;
void inline init()
{
for(register int i=2;i<=n;++i)
{
for(register int f=1;f*i<=n;++f)
{
value[otail++]=i*f;
for(register int k=0;k<otail;++k)
{
unable[value[otail-1]][value[k]]=unable[value[k]][value[otail-1]]=true;
}
}
otail=0;
}
}
int main()
{
//ios::sync_with_stdio(false);
//cin>>t>>n;
t=read();
n=read();
init();
while(t--)
{
//cin>>x>>y;
x=read();
y=read();
for(register int i=1;i<=n;++i)
{
//cin>>value[i];
value[i]=read();
result[i]=-1;
hsh[i]=false;
}
shortest_path(x);
//cout<<result[y]<<endl;
printf("%d\n",result[x]);
}
return 0;
}
```
~~题面强调开o2，比赛时候卡了一个多小时常数都没卡过去才发觉不对。（虽然我自带大常数）~~