题解 P4667 【[BalticOI 2011 Day1]Switch the Lamp On】
_虹_
2018-10-24 20:35:35
其实并不一定要手写堆。
感谢伟大的STL造福众生。
介绍一些stl提供的~~我第一次用的~~堆操作函数。
- （以下所有end都是数组尾的下一个元素）
- 生成堆：make_heap(T* begin,T* end)，将一个无序数组组织成堆。
- 插入值：在数组尾加上插入的数值，再调用push_heap(T* begin,T* end);维护堆的性质。
- 弹出堆顶：pop_heap(T* begin,T* end);江堆顶移动到队列尾部，其他部分维持堆的性质。
- 插入弹出要求数组已经是一个堆
没了优先队列底层的vector，不吸氧，堆+dij也就ac了。
~~跑了2758ms，最大点128ms。~~
```cpp
#include <iostream>
#include <algorithm>
//#include <memory.h>
using namespace std;
const unsigned int INT_MAX=2147483647;
const int kmaxn=260000;
const int kmaxm=kmaxn<<3;
/////////////////////////////////////////////////////
struct unit
{
int first;
int second;
unit():first(0),second(0){};
unit(int f,int s):first(f),second(s){};
const int operator<(const unit& u)const
{
return first>u.first;
}
};
class p_queue
{
unit heap[kmaxm];
int otail;
public:
p_queue():otail(0){};
unit top(){
pop_heap(&heap[0],&heap[otail]);
return heap[otail-1];
}
void pop(){otail--;//以前是优先队列写的dij，干脆就这样凑活一下，其实top里弹出要安全一些，毕竟pop_heap之后数组尾元素已经不符合堆的性质了。
}
void push(const unit v){
heap[otail++]=v;
push_heap(&heap[0],&heap[otail]);
}
const bool empty()const{return !otail;}
}q;
//////////////////////////////////////////////////////
struct edge
{
int dest=0;
long long int length=0;
edge* next=NULL;
};
const int max_pool_size=kmaxn<<2;
edge memory_pool[max_pool_size];
int pool_otail;
edge* list[kmaxn];//链式前向星是不会写的，这辈子也不会写前向星的
int result[kmaxn];
bool hsh[kmaxn];
void relax(int p)
{
edge* t=list[p];
while(t)
{
if(result[t->dest]>result[p]+t->length)
{
result[t->dest]=result[p]+t->length;
q.push(unit(result[t->dest],t->dest));
}
t=t->next;
}
}
void shortest_path(const int start)
{
for(register int i=0;i<kmaxn;++i)
result[i]=INT_MAX;
q.push(unit(0,start));
result[start]=0;
int count=0;
int t=0;
while(!q.empty())
{
t=q.top().second;
q.pop();
if(!hsh[t])
{
relax(t);
hsh[t]=true;
}
}
}
void add_edge(const int& s,const int &d,const long long int &w)
{
if(list[s])
{
memory_pool[pool_otail].next=list[s];
}
list[s]=&memory_pool[pool_otail++];
list[s]->dest=d;
list[s]->length=w;
}
////////////////////////////////////////////////////
int n,m;
char ch;
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
++n;
++m;
for(register int i=1;i<n;++i)
{
for(register int f=1;f<m;++f)
{
cin>>ch;
if(ch=='\\')
{
//map[i][m*i+f]=1;
add_edge(m*(i-1)+f,m*i+f+1,0);
add_edge(m*i+f+1,m*(i-1)+f,0);
add_edge(m*(i-1)+f+1,m*i+f,1);
add_edge(m*i+f,m*(i-1)+f+1,1);
}
else
{
add_edge(m*(i-1)+f,m*i+f+1,1);
add_edge(m*i+f+1,m*(i-1)+f,1);
add_edge(m*(i-1)+f+1,m*i+f,0);
add_edge(m*i+f,m*(i-1)+f+1,0);
}
}
}
shortest_path(1);
if(result[n*m]==INT_MAX)
{
cout<<"NO SOLUTION"<<endl;
}
else
{
cout<<result[n*m]<<endl;
}
return 0;
}
```
本人蒟蒻，希望各位神犇指出错误QAQ。~~还希望管理员给个通过。~~