JZOJ 4302 [NOIP 2015 시 뮬 레이 션 11.3] 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 이사장 은 남 은 카드 를 뒤 지 려 하지 않 기 때문에 실제 카드 점 을 사용 하기 전에 점괘 성공 가능성 이 있 는 지 를 먼저 계산한다.더 나 아가 점 치 는 데 성공 할 수 있다 면 점 치 는 데 걸 리 는 시간의 최소 치 를 계산 해 낼 것 이다.현재 카드 의 배열 정보 와 미리 결 정 된 조작 정 보 를 보 여 줍 니 다. 점괘 가 성공 할 수 있 는 지, 성공 할 수 있다 면 출력 소모 시간의 최소 치 를 계산 하 는 프로그램 을 작성 하 십시오.
Analysis
우선 I 를 1 로, O 를 0 으로.(비슷 하 게 생 겼 다) 이 문 제 는 'IOIOI' 로 고정된 포맷 이 특징 이다.01 꼬치 에 대해 서 는 인접 한 두 사람 에 게 이상 하거나 한 번 에 접근 할 수 있 음 을 발견 할 수 있다.I 와 O 의 전환점 인 xor 값 만 1 이기 때문에 이 또는 뒤의 꼬치 는 4 개의 1 과 그 안에 꽂 힌 0 더미 로 구성 된다.예 를 들 면:
111011011011 (원본 문자열)
혹은 그 다음 에:
00110100010 (A)
우 리 는 원 열 에 있 는 [3, 6] 구간 에서 반대로, 원 열 이 바 뀌 는 것 과 같은 조작 을 시 뮬 레이 션 합 니 다.
110100000011
한번 시도 해 보 세 요:
01110000010 (B)
(A) 와 (B) 의 관 계 를 찾 아 보 세 요.구간 [3, 6] 을 A 의 위 치 를 2, 6 으로 반값 하 는 것 을 발견 할 수 있다.일반적으로 구간 [l, r] 을 반 등가 로 하 는 것 은 A 중의 위치 l - 1, r 를 반 으로 하 는 것 이다.그럼 목표 문자열 (IIII... IIII) 에서 이상 하거나 일어나 면 하나 도 없어 요.그래서 모든 위 치 를 점 으로 추상 화 할 수 있 고 하나의 조작 은 자 연 스 럽 게 변 이 된다.변 권 은 r - l + 1 이다.그리고 4 개의 1 의 위치 에 대해 서 는 두 쌍 의 최 단 로 를 최소 화하 면 된다.
Code

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int N=500010,M=N*2;
const ll INF=4340410370284600380;
int tot,to[M],next[M],last[N];
ll wei[M],dis[3][N];
bool bz[N];
queue<int> q;
void link(int u,int v,ll w)
{
    to[++tot]=v;
    wei[tot]=w;
    next[tot]=last[u];
    last[u]=tot;
}
void SPFA(int u,int p)
{
    memset(bz,0,sizeof(bz));
    memset(dis[p],60,sizeof(dis[p]));
    dis[p][u]=0,bz[u]=1;
    q.push(u);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=last[u];i;i=next[i])
        {
            int v=to[i];
            if(dis[p][u]!=INF && dis[p][u]+wei[i]<dis[p][v])
            {
                dis[p][v]=dis[p][u]+wei[i];
                if(!bz[v])
                {
                    bz[v]=1;
                    q.push(v);
                }
            }
        }
        bz[u]=0;
    }
}
int main()
{
    freopen("card.in","r",stdin);
    freopen("card.out","w",stdout);
    int A,B,C,D,E,n,u,v;
    scanf("%d %d %d %d %d %d",&A,&B,&C,&D,&E,&n);
    int v0=A,v1=A+B,v2=A+B+C,v3=A+B+C+D;
    fo(i,1,n)
    {
        scanf("%d %d",&u,&v),u--;
        link(u,v,v-u),link(v,u,v-u);
    }
    SPFA(v0,0);SPFA(v1,1);SPFA(v2,2);
    ll ans=dis[0][v1]+dis[2][v3];
    ans=min(ans,dis[0][v2]+dis[1][v3]);
    ans=min(ans,dis[0][v3]+dis[1][v2]);
    printf("%lld",ans>=INF?-1:ans);
    fclose(stdin);fclose(stdout);
    return 0;
}