卡片占卜

NC53269. 卡片占卜

描述

译自 JOISC 2015 Day1 T4「IOIOI カード占い / IOIOI Cards」

K理事长是占卜好手，他精通各种形式的占卜。今天，他要用正面写着I，背面写着O的卡片占卜一下日本IOI国家队的选手选择情况。
占卜的方法如下：

首先，选取五个正整数A,B,C,D,E；
然后，拿出A+B+C+D+E张卡片摆成一排，从左至右摆成A张正面，B张反面，C张正面，D张反面，E张正面的形式。也就是说，从左到右依次摆A张I，B张O，C张I，D张O，E张I；
再从预先确定的N种操作中选择1种以上，然后按照自己喜欢的顺序进行操作，同样的操作可以进行1次及以上。第i种操作是「把从左到右第 $L_i$ 张卡片到第 $R_i$ 张卡片（包括两端）翻过来」，因为需要用手操作，所以翻1张牌需要花费1秒，完成一次操作需要花费 $R_i-L_i+1$ 秒；
操作后，如果所有牌都是正面朝上的，占卜就结束了。

因为这种占卜比较费时，所以K理事长在占卜之前想知道占卜能否结束，如果能结束，他想知道占卜的最小耗时。

输入描述

第一行，五个正整数A,B,C,D,E，意义如题目描述；
第二行，一个正整数N，意义如题目描述；
接下来N行描述操作，一行两个正整数，意义如题目描述。

输出描述

输出一行，如果占卜能够结束，则输出一个正整数，表示占卜的最小耗时；如不能，输出-1。

示例1

输入:

输出:

说明:

最初的卡片序列为IOOIIIOOOOIIIII；
先进行第二个操作，卡片序列变为IIIOOOOOOOIIIII，花费5秒；
再进行第三个操作，卡片序列变为IIIIIIIIIIII，这个操作花费7秒，一共花费12秒。
可以证明，12秒为占卜的最小耗时，因此输出12。

示例2

输入:

1 1 1 1 1
1
1 1

输出:

-1

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 78ms, 内存消耗: 8952K, 提交时间: 2020-08-12 19:44:31

#include<bits/stdc++.h>
#define LL long long
#define _(d) while(d(isdigit(ch=getchar())))
using namespace std;
int R(){
    int x;bool f=1;char ch;_(!)if(ch=='-')f=0;x=ch^48;
    _()x=(x<<3)+(x<<1)+(ch^48);return f?x:-x;}
const int N=5e5+5;
int n,a[6],head[N],cnt;LL dis[N],ans=2e18;
struct edge{int to,nex,w;}e[N<<1];
struct node{
    int x;LL w;
    bool friend operator <(node a,node b){return a.w>b.w;}
};priority_queue<node>q;
void add(int s,int t,int w){e[++cnt]=(edge){t,head[s],w},head[s]=cnt;}
void dij(int s){
    for(int i=0;i<=a[5];i++)dis[i]=2e18;
    dis[s]=0;
    q.push((node){s,0});
    while(!q.empty()){
        node now=q.top();q.pop();
        if(now.w!=dis[now.x])continue;
        for(int v,k=head[now.x];k;k=e[k].nex)
            if(dis[v=e[k].to]>dis[now.x]+e[k].w)
                dis[v]=dis[now.x]+e[k].w,q.push((node){v,dis[v]});
    }
    return;
}
int main(){
    for(int i=1;i<=5;i++)a[i]=a[i-1]+R();
    n=R();
    for(int i=1,u,v;i<=n;i++)
        u=R()-1,v=R(),add(u,v,v-u),add(v,u,v-u);
    dij(a[1]);
    LL s1=dis[a[2]],s2=dis[a[3]],s3=dis[a[4]];
    dij(a[2]);
    ans=min(min(ans,s2+dis[a[4]]),s3+dis[a[3]]);
    dij(a[3]);
    ans=min(ans,s1+dis[a[4]]);
    printf("%lld\n",ans==2e18?-1:ans);
    return 0;
}