[차분 제약] poj 2983: Is the Information Reliable?

대체로 제목:    n 개 점 의 m 조 제약 정 보 를 드 립 니 다.모든 정 보 는 (P a b c) a 가 b 북방 거리 c 의 위 치 를 나타 내 거나 (V a b) a 가 b 북방 1 단위 거리 또는 더 먼 위 치 를 나타 낸다.상기 m 개 요구 에 부합 하 는 점 이 있 을 수 있 는 지 물 었 다.
대체적인 사고방식:    dis [i] 를 시작 점 까지 의 거리 로 설정 합 니 다.두 번 째 조건 은 간단 하 다 dis [a] - dis [b] > = 1 즉 dis [b] < = dis [a] - 1.첫 번 째, 같은 번 호 를 가 진 조건 dis [a] - dis [b] = c 에 대해 우 리 는 dis [a] - dis [b] > = c 와 dis [a] - dis [b] < = c 두 개의 부등식 으로 전환 한 다음 에 최 단 로 삼각형 부등식 으로 전환 할 수 있다.모든 점 이 서로 연결 되 지 않 기 때문에 가상 시점 을 설정 하고 모든 점 과 연결 되 며 길 이 는 0 으로 설정 해 야 합 니 다.그리고 spfa 로 가능 여 부 를 판정 해 주시 면 됩 니 다.    닦 아, 닦 아. 내 가 반년 동안 사용 한 spfa 대기 열 모델 에 bug 가 있 었 는데 하룻밤 동안 bug 를 찾 아서 야 ac 가 떨 어 졌 다.진심 이 야.

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax=200050;
const int mMax=1000050;
const int inf=1<<28;
struct{
    int u,v, next;
    int  w;
}edge[mMax];
int n, k, head[nMax];
int dis[nMax];
int que[nMax],m,sum[nMax];
bool vis[nMax];

void addedge(int a,int b,int w){
    edge[k].w = w;
    edge[k].u=a;
    edge[k].v=b;
    edge[k].next=head[a];
    head[a]=k;k++;
}

bool spfa(int s){      //  ，  ，   
    int i, hhead = 0, tail = 1;    //                             
    for(i = 0; i <= n; i ++){
        dis[i] = inf;////////////
        vis[i] = false;
    }
    dis[s] = 0;
    que[0] = s;
    vis[s] = true;
    while(tail != hhead){     //        。
        int u = que[hhead];
        vis[u] = false;
        for(int p = head[u]; p != 0; p = edge[p].next){
            int v = edge[p].v;     //     edge[k].v，WA   。
            if(dis[v] > dis[u] + edge[p].w){
                dis[v] = dis[u] + edge[p].w;
                if(!vis[v]){
                    vis[v] = true;
                    que[tail ++] = v;
                    if(tail == nMax) tail = 0;
                    if(++sum[v] > n) return false;     //          。
                }
            }
        }
        hhead ++;
        if(hhead == nMax) hhead = 0;
    }
    return 1;
}

int main(){
    int m,i,j,a,b,c,s;
    char str[20];
    while(cin>>n>>m){
        s=0;
        k=1;
        memset(sum,0,sizeof(sum));
        memset(head,0,sizeof(head));
        while(m--){
            scanf("%s",str);
            if(str[0]=='P'){
                scanf("%d%d%d",&amp;a,&amp;b,&amp;c);
                addedge(b,a,c);
                addedge(a,b,-c);
            }
            else{
                scanf("%d%d",&amp;a,&amp;b);
                addedge(a,b,-1);
            }
        }
        for(i=1;i<=n;i++){
            addedge(s,i,0);
        }
        if (spfa(s))
            printf("Reliable
");
        else
            printf("Unreliable
");
    }
    return 0;
}