IOIOI 카드 점

제목 설명
K 이사장 은 점 치 기 를 좋아해 다양한 방식 으로 점 치 곤 했다.오늘 그 는 'I' 라 고 정면으로 쓰 여 있 고, 반대로 'O' 라 고 쓰 여 있 는 카드 로 올해 IOI 의 일본 대표 팀 이 최종 성적 을 점 치 려 고 한다.점 치 는 방법 은 다음 과 같다. 우선 5 개의 정수 A, B, C, D, E 를 선택한다.IOI 카드 A + B + C + D + E 장 을 한 줄 로 세우 고 맨 왼쪽 에 있 는 A 장의 카드 는 정면 을 위로 향 한 다음 B 장의 뒷면 을 위로 향 한 다음 C 장의 카드 는 정면 을 위로 향 한 다음 D 장의 뒷면 을 위로 향 한 다음 E 장의 정면 을 위로 향 한 것 이다.이렇게 배열 하면 왼쪽 부터 차례대로 A 장 'I', B 장 'O', C 장 'I', D 장 'O', E 장 'I' 가 된다.미리 결 정 된 N 가지 조작 중 최소 1 가 지 를 골 라 임 의 순서에 따라 집행 한다.(비고: 같은 조작 을 여러 번 실행 해도 됩 니 다.) 여기 서 i 번 째 조작 (1 < = i < = N) 은 [왼쪽 에서 Li 번 째 카드 부터 Ri 번 째 카드 까지 모두 뒤 집 습 니 다] 입 니 다.카드 한 장 을 뒤 집 는 데 1 초가 걸 리 기 때문에 i 번 째 조작 은 리 리 + 1 초가 걸린다.조작 이 끝 난 후 모든 카드 가 정면으로 향 하면 점 치 는 데 성공 한다.K 이사장 은 남 은 카드 를 뒤 지 려 하지 않 기 때문에 실제 카드 점 을 사용 하기 전에 점괘 성공 가능성 이 있 는 지 를 먼저 계산한다.더 나 아가 점 치 는 데 성공 할 수 있다 면 점 치 는 데 걸 리 는 시간의 최소 치 를 계산 해 낼 것 이다.현재 카드 의 배열 정보 와 미리 결 정 된 조작 정 보 를 보 여 줍 니 다. 점괘 가 성공 할 수 있 는 지, 성공 할 수 있다 면 출력 소모 시간의 최소 치 를 계산 하 는 프로그램 을 작성 하 십시오.
차이 점
신기 한 차이 점!원래 서열 과 인접 한 두 항목 을 다른 것 으로 만 들 거나 새로운 서열 을 얻 을 수 있다.그러면 새로운 서열 은 4 개의 1 만 있 고 목 표 는 일련의 조작 을 통 해 1 의 개 수 를 0 으로 바 꾸 는 것 이다.한 번 의 조작 [l, r] 은 새로운 서열 에서 l - 1 과 r 를 반대 하 는 것 과 같다.조작 [l, r] 을 l - 1 방향 r 의 방향 이 없고 권한 값 은 조작의 시간 소모 로 간주한다.1 이 두 개 밖 에 없다 면, 답 은 가장 짧 은 길이 다.최 단 로 는 고리 가 생기 지 않 기 때문에 시작 점 과 끝 점 을 제외 하고 모두 두 번 지나 가 며 자신 은 변 하지 않 는 다.출발점 과 종점 은 한 번 만 지나 면 0 에서 1 로 바뀐다.4 개 1 이면 폭력 2 개가 일치 하 는 최 단 로 를 만 들 고 최소 치 를 취하 면 된다.DIJ 제 가 시간 을 초과 해서 SPFA 를 쳤 는데 효과 가 있 더 라 고요.

#include
#include
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int maxn=500000+10;
int h[maxn],go[maxn*2],dis[maxn*2],next[maxn*2],id[maxn];
int dl[maxn];
bool bz[maxn];
int a[5];
int i,j,k,l,r,n,m,tot,top;
ll t,ans,inf,f[maxn];
void add(int x,int y,int z){
    if (!bz[x]){
        bz[x]=1;
        id[++top]=x;
    }
    if (!bz[y]){
        bz[y]=1;
        id[++top]=y;
    }
    go[++tot]=y;
    dis[tot]=z;
    next[tot]=h[x];
    h[x]=tot;
}
ll spfa(int x,int y){
    int i,t,now,l,r;
    fo(i,1,top) f[id[i]]=inf+1,bz[id[i]]=0;
    f[x]=0;
    bz[x]=1;
    dl[r=1]=x;
    l=0;
    while (l!=r){
        l=l%top+1;
        now=dl[l];
        t=h[now];
        while (t){
            if (f[now]+dis[t]if (!bz[go[t]]){
                    r=r%top+1;
                    dl[r]=go[t];
                    bz[go[t]]=1;
                }
            }
            t=next[t];
        }
        bz[now]=0;
    }
    return f[y];
}
int main(){
    freopen("card.in","r",stdin);freopen("card.out","w",stdout);
    scanf("%d%d%d%d%d",&j,&k,&l,&r,&t);
    a[1]=j;
    a[2]=j+k;
    a[3]=j+k+l;
    a[4]=j+k+l+r;
    n=j+k+l+r+t;
    scanf("%d",&m);
    fo(i,1,m){
        scanf("%d%d",&j,&k);
        add(j-1,k,k-j+1);add(k,j-1,k-j+1);
        inf+=(ll)k-j+1;
    }
    fo(i,1,4){
        fo(j,1,top+1)
            if (j>top||id[j]==a[i]) break;
        if (j>top){
            printf("-1
");
            return 0;
        }
    }
    ans=inf+1;
    fo(i,1,3)
        fo(j,i+1,4){
            t=spfa(a[i],a[j]);
            fo(k,1,4)
                if (k!=i&&k!=j) break;
            fo(l,1,4)
                if (l!=i&&l!=j&&l!=k) break;
            t+=spfa(a[k],a[l]);
            ans=min(ans,t);
        }
    if (ans==inf+1) printf("-1
");else printf("%lld
",ans);
}