第十五届四川省省赛 SCU

给你一个一共由两种边的完全图 要求你求1到N的最短路

q队列为前沿队列(已探索过且最外围的点)  p队列为未探索队列(未探索过的点)

depth这个数组的用法并不是代表实际上这个点在第几层 而是防止死循环 保证每次通过前沿的一个点都只会遍历p中每个点一次

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long mod = 1e9+7;
const int maxn = 5e5+5;
const int inf = 1e9+7;
int n,m,a,b,nm,qwq;
int head[maxn];
ll dis[maxn];
struct node{
    int to,nxt;
}edg[maxn*2];
void add(int x,int y){
    edg[++nm].to = y;
    edg[nm].nxt = head[x];
    head[x]=nm;
    if(x==1&&y==n)qwq=1;
}
queue<int> p,q;
int f[maxn],dep[maxn];
void solve(){
    dis[1]=0;
    int i,j,x,y;
    p.push(1);
    for(i=2;i<=n;i++){
        q.push(i);
    }
    for(i=1;i<=n;i++){
        f[i]=0;dep[i]=0;
    }
    while(!p.empty()){
        if(q.empty())break;
        x = p.front();
        p.pop();
        for(i=head[x];i;i=edg[i].nxt)f[edg[i].to]=x;
        j = dep[q.front()];
        while(!q.empty()){
            y = q.front();
            if(dep[y]!=j)break;  
            q.pop();
            dep[y]=dep[y]+1;
            if(f[y]==x)q.push(y);
            else{
                p.push(y);
                dis[y]=dis[x]+b;
            }
        }
    }
    while(!p.empty())p.pop();
    while(!q.empty())q.pop();
    if(dis[n]==-1||dis[n]>a)printf("%d
",a);
    else printf("%lld
",dis[n]);
}

void dist(){
    int i,j,x,y;
    dis[1]=0;
    p.push(1);
    while(!p.empty()){
        x = p.front();
        p.pop();
        for(i=head[x];i;i=edg[i].nxt){
            y = edg[i].to;
            if(dis[y]!=-1)continue;
            dis[y]=dis[x]+a;
            p.push(y);
        }
    }
    if(dis[n]==-1||dis[n]>b)printf("%d
",b);
    else printf("%lld
",dis[n]);
}
int main()
{
    while(scanf("%d%d%d%d",&n,&m,&a,&b)==4){
        qwq=0;
        nm = 0;
        int i,j,x,y;
        for(i=1;i<=n;i++){
            head[i]=0;
            dis[i]=-1;
        }
        for(i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }
        if(a>=b){
            if(qwq==0){
                printf("%d
",b);
            }
            else solve();
        }
        else{
            if(qwq==1){
                printf("%d
",a);
            }
            else dist();
        }
    }
}