문제 풀이 P5037 [체포]

관례 대로 먼저 허튼소리 를 하 다.
P4473 [국가 합숙 대] 비 협 을 해 보 셨 는 지 모 르 겠 어 요.만약 해 본 적 이 없다 면 가서 볼 수 있다. 그 문제 의 이 문 제 는 바로 비 협 의 최적화 사상 을 사용 한 것 이다.한 번 의 시험 에서 우 리 는 비 협 이라는 문 제 를 시험 한 후에 표지 판 은 층 을 나 누 는 그림 이 었 다. 내 가 너무 못 알 아 듣 기 때문에 인터넷 에서 검색 하여 설명 한 결과 신선 한 알고리즘 을 발견 했다. Dijkstra + 와 최적화 (나중에 Zcy sky 큰 놈 도 낙 곡 에서 관련 문 제 를 풀 었 고 나 도 염치없게 한 편 을 보 냈 다. 여 기 는 말 하지 않 겠 다)알 아 본 후에 나 는 그 문제 의 최적화 방향 을 여기에 활용 했다. QAQ.
다 풀 었 으 니 다음은 문 제 를 이야기 하 겠 습 니 다.
먼저 문 제 를 간소화 합 니 다. 번 호 를 $1 $에서 $n $의 $n $개 점 으로 줄 것 입 니 다. 두 번호 가 서로 연 결 된 점 은 연결 할 수 있 습 니 다. 같은 점 에서 출발 하 는 변 가중치 가 같 습 니 다. 주어진 두 점 사이 의 가장 짧 은 길 을 찾 습 니 다. (사실은 $1 $호 점 을 제외 하고 나머지 모든 점 은 서로 연결 되 어 있 습 니 다. 관례 에 따라 $- 1 $의 데 이 터 를 출력 하 는 것 은 존재 하지 않 습 니 다)
제목 은 크게 $2 $부분 으로 나 뉜 다. 1. $n $이내 의 상호 질점 을 매 거 한다.2. 최 단 로 를 구한다
첫 번 째 부분 에 대해 저 는 폭력 매 거 를 끊 고 구조 법 만 시 키 려 고 했 지만 $n $가 너무 작 아서 구조 가 폭력 매 거 보다 더 느리게 달 렸 습 니 다.
그래도 구조 법의 사고방식 을 말씀 해 주세요.
1. 우선 $1 $~ $n $의 모든 질 수 를 미리 처리 합 니 다.
2. 매 거 $i = 1 $~ $n $
3. 각각 $i $에 대해 서 는 질량 인 수 를 분해 하여 그 질 수 를 사용 하 였 습 니 다.
4. $i $에서 사용 하지 않 은 질 수 를 선택 하여 조합 하여 $i $보다 작 게 합 니 다.
코드 는 다음 과 같 습 니 다 (최 단 로 부분 이 최적화 되 지 않 았 습 니 다).

#include
#define ll long long
#define INF 0x7f7f7f7f
using namespace std;
const int maxn = 105;
ll x[50010],Ans1,Su[10010],Fa[10010],Cnt,Ans,n,X,Dist[10010],w[10010];
bool Pd[10010],Used[10010],From[10010][10010];
int T,u,v,Head[10010],To[61000010],Next[61000010];
queue Q;
struct Node {
    int p,Dis;
} Now,N;
bool operator y.Dis;
}
priority_queue PQ;
template 
inline int Read(T &x) {
    x=0;
    int f=1;
    char c=getchar();
    while(c!='-'&&c>'9'&&c9) {
        Write((x-x%10)/10);
    }
    putchar(x%10+'0');
}
inline ll Multi(ll a, ll b, ll p) {
    ll Ans1 = 0;
    while(b) {
        if(b & 1LL) Ans1 = (Ans1+a)%p;
        a = (a+a)%p;
        b >>= 1;
    }
    return Ans1;
}
inline ll QPow(ll a, ll b, ll p) {
    ll Ans1 = 1;
    while(b) {
        if(b & 1LL) Ans1 = Multi(Ans1, a, p);
        a = Multi(a, a, p);
        b >>= 1;
    }
    return Ans1;
}
inline bool MR(ll n) {
    if(n == 2)  return true;
    int s = 20, i, t = 0;
    ll u = n-1;
    while(!(u&1)) {
        t++;
        u >>= 1;
    }
    while(s--) {
        ll a = rand()%(n-2)+2;
        x[0] = QPow(a, u, n);
        for(i = 1; i <= t; i++) {
            x[i] = Multi(x[i-1], x[i-1], n);
            if(x[i] == 1 && x[i-1] != 1 && x[i-1] != n-1)   return false;
        }
        if(x[t] != 1)   return false;
    }
    return true;
}
inline ll Gcd(ll a, ll b) {
    if(b == 0)
        return a;
    else
        return Gcd(b, a%b);
}
inline ll Pollard_Rho(ll n, int c) {
    ll i = 1, k = 2, x = rand()%(n-1)+1, y = x;
    while(1) {
        i++;
        x = (Multi(x, x, n)+c)%n;
        ll p = Gcd((y-x+n)%n, n);
        if(p != 1 && p != n)    return p;
        if(y == x)  return n;
        if(i == k) {
            y = x;
            k <<= 1;
        }
    }
}
inline void Find(ll x, int c) {
    if(x == 1)  return;
    if(MR(x)) {
        Pd[x]=1;
        return;
    }
    ll p = x, k = c;
    while(p >= x) {
        p = Pollard_Rho(p, c--);
    }
    Find(p, k);
    Find(x/p, k);
}
inline void Add(int a,int b) {
    To[++Cnt]=a;
    Next[Cnt]=Head[b];
    Head[b]=Cnt;
    To[++Cnt]=b;
    Next[Cnt]=Head[a];
    Head[a]=Cnt;
}
void Dijkstra(int x) {
    Dist[x]=0;
    Now.Dis=0;
    Now.p=x;
    PQ.push(Now);
    while(!PQ.empty()) {
        Now=PQ.top();
        From[Now.p][0]=0;
        PQ.pop();
        if(!Pd[Now.p]) {
            Pd[Now.p]=1;
            for(int i=Head[Now.p]; i; i=Next[i]) {
                if(!Pd[To[i]]&&(!From[Now.p][Fa[To[i]]])&&(Dist[To[i]]>Dist[Now.p]+w[Now.p])) {
                    Fa[To[i]]=Now.p;
                    Dist[To[i]]=Dist[Now.p]+w[Now.p];
                    From[To[i]][Now.p]=1;
                    N.p=To[i];
                    N.Dis=Dist[Now.p]+w[Now.p];
                    PQ.push(N);
                }
            }
        }
    }
}
int main() {
    Read(T);
    Read(n);
    Cnt=0;
    for(int i=2; i<=5000; i++) {
        if(MR(i)) {
            Su[++Cnt]=i;
        }
    }
    Cnt=0;
    for(int i=1; i<=n; i++) {
        memset(Pd,0,sizeof(Pd));
        memset(Used,0,sizeof(Used));
        Find(i,57);
        for(int j=1; Su[j]

두 번 째 부분 에 대해 서 는 모두 가 Dijkstra + 더미 최적화 라 고 쓸 것 이 라 고 믿 습 니 다. 그러면 50 점 을 쉽게 얻 을 수 있 습 니 다.
그럼 나머지 50 점 은 요?
사실 문 제 를 자세히 살 펴 보면 우 리 는 같은 점 에서 출발 하 는 변 의 가중치 가 모두 같다 는 것 을 알 수 있다. 그러면 우 리 는 점 을 우선 대기 열 에 눌 렀 을 때 현재 점 의 점 권 (즉, 현재 점 에서 출발 하 는 변 의 가중치) 을 직접 추가 할 수 있다. 우선 대기 열의 성질 때문에 매번 우선 대기 열 에서 꺼 내 는 점 은 그 상태 가 가장 좋 을 것 이다.그리고 그 확 대 된 상태 도 가장 좋다.증명 은 다음 과 같다.
$x $가 최 단 로 를 얻 었 다 고 가정 하면 이 점 으로 업 데 이 트 된 $y $도 최 단 로 를 얻 었 음 을 증명 합 니 다.
반증, 존재 경로 $x $′ → $y $
$Dist [y] $를 더 작 게 하고 $x $가 $y $를 업데이트 한 후 $Dist [x $′ $] + w [x] 가 있 습 니 다.
사실 비 협 의 증명 과 같 습 니 다.
이렇게 되면 점 마다 처음 방문 하 는 것 이 가장 좋 기 때문에 필요 한 점 을 찾 으 면 바로 물 러 날 수 있 습 니 다.
코드 는 다음 과 같 습 니 다:

#include
#define ll long long
#define INF 0x7f7f7f7f
using namespace std;
const int maxn = 105;
ll x[50010],Ans1,Su[5010],Cnt,Ans,n,X,Dist[5010],w[5010],Da;
bool Pd[5010],Used[5010];
int T,u,v,Head[5010],To[15000010],Next[15000010];
queue Q;
struct Node {
    int p,Dis;
} Now,N;
bool operator y.Dis;
}
priority_queue PQ;
template 
inline int Read(T &x) {
    x=0;
    int f=1;
    char c=getchar();
    while(c!='-'&&c>'9'&&c9) {
        Write((x-x%10)/10);
    }
    putchar(x%10+'0');
}
//            
inline ll Gcd(ll a, ll b) {
    if(b == 0)
        return a;
    else
        return Gcd(b, a%b);
}
inline void Add(int a,int b) {
    To[++Cnt]=a;
    Next[Cnt]=Head[b];
    Head[b]=Cnt;
    To[++Cnt]=b;
    Next[Cnt]=Head[a];
    Head[a]=Cnt;
}
void Dijkstra(int x) {
    Dist[x]=w[x];
    Now.Dis=w[x];
    Now.p=x;
    PQ.push(Now);
    while(!PQ.empty()) {
        Now=PQ.top();
        PQ.pop();
        if(!Pd[Now.p]) {
            Pd[Now.p]=1;
            for(int i=Head[Now.p]; i; i=Next[i]) {
                if(!Pd[To[i]]&&(Dist[To[i]]>Now.Dis)) {
                    if(To[i]==v){
                        Da=Now.Dis;
                        return;
                    }
                    Dist[To[i]]=Now.Dis;
                    N.p=To[i];
                    N.Dis=Dist[To[i]]+w[To[i]];
                    PQ.push(N);
                }
            }
        }
    }
}
int main() {
    Read(T);
    Read(n);
    Cnt=0;
    for(int i=2;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(Gcd(i,j)==1){
                Add(i,j);
            }
        }
    }
    while(T--) {
        fill(Dist,Dist+n+5,INF);
        memset(Pd,0,sizeof(Pd));
        Read(u);
        Read(v);
        for(int i=1; i<=n; i++) {
            Read(w[i]);
        }
        Dijkstra(u);
        Write(Da);
        putchar('
');
        while(!PQ.empty()){
            PQ.pop();
        }
    }

    return 0;
}