[BZOJ 4152]The Captain

danihao123 posted @ 2016年7月30日 14:34 in 题解 with tags BZOJ AMPPZ 最短路 Dijkstra 可并堆 pb_ds , 587 阅读
转载请注明出处:http://danihao123.is-programmer.com/

这题初看有些棘手。但是毕竟是最短路,[tex]min(abs(x_{1}-x_{2}),abs(y_{1}-y_{2}))[/tex]这样的边,大可以分成两条边来建,于是乎min就形同虚设了。并且我们可以看到这样建图有一个好处:跨越若干点的方案可以一定可以分成图上的若干边。问题大为简化,迎刃而解。

但这提有个丧病的地方:卡SPFA。加了一些优化照样挂。所以我一气之下写了可并堆优化的Dijkstra :)当然可并堆用的是pb_ds辣。

代码:

/**************************************************************
    Problem: 4152
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4888 ms
    Memory:17412 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <utility>
#include <ext/pb_ds/priority_queue.hpp>
#include <cctype>
#include <bitset>
#ifdef DEBUG
#include <cassert>
#endif
using namespace std;
const int maxn=200001;
int n;
inline int abs(int x){
    return x<0?-x:x;
}
  
int first[maxn];
int next[maxn*4],to[maxn*4],dist[maxn*4];
int graph_cnt=0;
inline void Add_Edge(int x,int y,int d){
    graph_cnt++;
    next[graph_cnt]=first[x];
    first[x]=graph_cnt;
    to[graph_cnt]=y;
    dist[graph_cnt]=d;
}
  
int d[maxn];
bitset<maxn> vis;
typedef pair<int,int> my_pair;
typedef __gnu_pbds::priority_queue<my_pair,greater<my_pair> > Heap;
Heap::point_iterator ite[maxn];
Heap Q;
int dij(){
    register int i,u;
    memset(d,0x7f,sizeof(d));
    d[1]=0;
    ite[1]=Q.push(make_pair(0,1));
    while(!Q.empty()){
        u=Q.top().second;
        Q.pop();
        if(vis[u])
            continue;
        vis[u]=true;
        for(i=first[u];i;i=next[i]){
            if(d[to[i]]>(dist[i]+d[u])){
                d[to[i]]=dist[i]+d[u];
                if(ite[to[i]]!=0)
                    Q.modify(ite[to[i]],make_pair(d[to[i]],to[i]));
                else
                    ite[to[i]]=Q.push(make_pair(d[to[i]],to[i]));
            }
        }
    }
    return d[n];
}
  
int pr[maxn][2];
int order1[maxn],order2[maxn];
int cmp1(const int i,const int j){
    return pr[i][0]<pr[j][0];
}
int cmp2(const int i,const int j){
    return pr[i][1]<pr[j][1];
}
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int main(){
    register int i;
    n=readint();
    for(i=1;i<=n;i++){
        pr[i][0]=readint();
        pr[i][1]=readint();
        order1[i]=i;
        order2[i]=i;
    }
    sort(order1+1,order1+1+n,cmp1);
    sort(order2+1,order2+1+n,cmp2);
    for(i=1;i<=n;i++){
        if(i!=1){
            Add_Edge(order1[i],order1[i-1],pr[order1[i]][0]-pr[order1[i-1]][0]);
            Add_Edge(order2[i],order2[i-1],pr[order2[i]][1]-pr[order2[i-1]][1]);
        }
        if(i!=n){
            Add_Edge(order1[i],order1[i+1],pr[order1[i+1]][0]-pr[order1[i]][0]);
            Add_Edge(order2[i],order2[i+1],pr[order2[i+1]][1]-pr[order2[i]][1]);
        }
    }
    printf("%d\n",dij());
    return 0;
}
questionpaper2022.i 说:
Jul 02, 2023 11:47:23 AM

Under the moniker questionpaper2022, a group of qualified writers has come together to offer specialised journalistic coverage of current events across the country. Our team consists of professional writers and citizen journalists with a variety of media interests who are dedicated to providing questionpaper2022.in education updates in the public interest while ensuring openness.In order to present the true image of current events, our reporting team intends to publish the Education & Recruitment Update for all age groups.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter