SPFA 최적화

오늘 경기 는 소박한 SPFA 판정 에 걸려 시간 초과 로 30 = = = 그러나 bzoj 에서는 AC 의 것 이다
최적화:
Orange Group: SLF 및 LLL 최적화
반복 최적화 (가지치기)

귀속 최적화

소박한 SPFA를 DFS 버전으로 바꿨습니다.
디스 d i s 그룹을 초기화해야 합니다.

코드

#include
#include
#include
#define N 10000
#define E 30000
using namespace std;
int dis[N];bool used[N];
int Next[E],Last[E],Len[E],End[E],cnt;
void Ins(int x,int y,int v){
    End[++cnt]=y,Next[cnt]=Last[x],Last[x]=cnt,Len[cnt]=v;
}
bool SPFA(int u){
    used[u]=true;// ， 
    for(int i=Last[u];i;i=Next[i]){
        int v=End[i];
        if(dis[u]+Len[i]if(used[v])return true;
            dis[v]=dis[u]+Len[i];
            if(SPFA(v))return true;
        }
    }
    used[u]=false;return false;
}
int main(){
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)dis[i]=1e9;// 
    for(int i=1;i<=m;i++){
        int id,a,b,c;scanf("%d",&id);
        if(id==1){scanf("%d%d%d",&a,&b,&c);Ins(b,a,c);}
        if(id==2){scanf("%d%d%d",&a,&b,&c);Ins(b,a,-c);}
        if(id==3){scanf("%d%d",&a,&b);Ins(b,a,0),Ins(a,b,0);}
    }
    for(int i=1;i<=n;i++)Ins(n+1,i,0);
    if(SPFA(n+1))puts("No");else puts("Yes");
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

HDU 3631 Shortest Path(Floyd + 플러그인)

제목: n개의 점 m줄 테두리(단방향 테두리)와 q차 조작을 드리겠습니다. 처음에는 모든 점이 표시가 없습니다. 두 가지 조작이 있습니다. 1.0 x: x를 표시하고 가까이 표시한 경우 "ERROR! At point...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다