[NOIP 2015] IOIOI 카드 점

Description
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 이사장 은 남 은 카드 를 뒤 지 려 하지 않 기 때문에 실제 카드 점 을 사용 하기 전에 점괘 성공 가능성 이 있 는 지 를 먼저 계산한다.더 나 아가 점 치 는 데 성공 할 수 있다 면 점 치 는 데 걸 리 는 시간의 최소 치 를 계산 해 낼 것 이다.현재 카드 의 배열 정보 와 미리 결 정 된 조작 정 보 를 보 여 줍 니 다. 점괘 가 성공 할 수 있 는 지, 성공 할 수 있다 면 출력 소모 시간의 최소 치 를 계산 하 는 프로그램 을 작성 하 십시오.
Solution
와, 데이터 구조 같 지만 데이터 구 조 를 사용 할 수 는 없 을 거 야.아무리 생각해 도 생각 지도 못 했 어 요. 20 점 을 받 고 문 제 를 보 니 순간 폭발................................................
차이 점
01 서열 이기 때문에 매번 에 한 단락 의 서열 을 반 으로 취하 고 중간의 이 또는 값 은 변 하지 않 으 며 단점 과 양쪽 의 이 또는 값 만 변 한다. 그러면 우 리 는 01 서열 을 두 개의 이 또는 값 으로 바 꾸 고 매번 l 을 r 구간 에서 반 으로 취하 면 차이 점 후의 서열 l - 1 과 r 를 반 으로 취 하 는 것 과 같다.어떻게 생각 했 는 지 모 르 겠 어 요.
문제 전환
현재 문 제 는 01 서열 로 바 뀌 었 다. 중간 에 4 개의 1 만 있 고 주어진 두 개의 점 을 반 으로 (여러 번 취 할 수 있다) 하 며 서열 을 모두 0 의 서열 로 바 꾸 도록 요구한다.두 가지 가 언급 된 이상 의존 관계 가 있 으 니 우 리 는 연 계 를 고려 해 보 자.한 변 을 다 걸 을 때마다 두 점 의 값 을 반대 하 는 것 이다. 차이 점 이기 때문에 i 에서 j 까지 걸 어가 고 j 에서 k 까지 걸 어가 면 이 두 단락 의 차이 점 구간 이 교차 하지만 실제 구간 은 인접 하기 때문에 연 변 은 구간 의 취 반 은 후 효 성 이 없 을 수 있다.그러면 우 리 는 각 1 의 위치 에 대해 spfa 를 한 번 하고 두 쌍 의 점 을 매 거 합 니 다. 두 쌍 의 최 단 로 와 바로 현재 의 답 입 니 다. 최종 답 은 최소 치 로 가면 됩 니 다.정 답 조심 하 세 요. int 터 집 니 다.
Code

#include
#include
#include
#include
#include
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=500007;
int i,j,k,l,t,n,m;
long long ans,ans1;
int a,b,c,dd,e;
int first[maxn*2],next[maxn*2],last[maxn*2],chang[maxn*2],num;
int g[4],data[maxn*3];
long long d[4][maxn],da;
bool bz[maxn];
void add(int x,int y,int z){
    last[++num]=y;
    next[num]=first[x];
    first[x]=num;
    chang[num]=z;
}
void spfa(int x,int y){
    int i,j,k,head=0,tail=1,now;
    memset(bz,0,sizeof(bz));
    memset(data,0,sizeof(data));
    fo(i,0,maxn)d[y][i]=99999999999;
    da=d[y][0];
    d[y][x]=0;
    bz[x]=1;data[tail]=x;
     while(headfor(i=first[now];i;i=next[i]){
            if(d[y][now]+chang[i]y][last[i]]){
                d[y][last[i]]=d[y][now]+chang[i];
                if(!bz[last[i]]){
                    bz[last[i]]=1;
                    data[++tail]=last[i];
                }
            }
        }
        bz[now]=0;
    }
}
int main(){
    freopen("card.in","r",stdin);
    freopen("card.out","w",stdout);
    scanf("%d%d%d%d%d",&a,&b,&c,&dd,&e);
    g[0]=a;g[1]=a+b;g[2]=a+b+c;g[3]=a+b+c+dd;
    scanf("%d",&n);
    fo(i,1,n){
        scanf("%d%d",&k,&t);
        add(k-1,t,t-k+1);
        add(t,k-1,t-k+1);
    }
    bool az[4]={0,0,0,0};
    spfa(g[0],0);
    spfa(g[1],1);
    spfa(g[2],2);
    spfa(g[3],3);
    ans=99999999999;
    fo(i,0,3){
        az[i]=1;
        fo(j,i+1,3){
            az[j]=1;
            fo(k,0,3){
                if(!az[k]){
                    az[k]=1;
                    fo(l,0,3){
                        if(!az[l]){ 
                            ans1=d[i][g[j]]+d[k][g[l]];            
                            ans=min(ans,ans1);
                        }
                    }
                    az[k]=0;
                }
            }
            az[j]=0;
        }
        az[i]=0;
    }
    if(ans>=da)printf("-1
");
    else printf("%lld
",ans);
}