WA ON #2#3#6求助
查看原帖
WA ON #2#3#6求助
906856
A2_Zenith楼主2023/8/25 16:25
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdlib>
#include<iomanip>
#include<map>
#define int long long
#define db long double
#define lc(p) p<<1
#define rc(p) p<<1|1
#define pii pair<int,int>
#define up(i,l,r) for(int i=(l);i<=(r);i++)
#define down(i,l,r) for(int i=(l);i>=(r);--i)
#define p_b push_back
#define m_p make_pair
using namespace std;
int n,m,k,s;
int p,q;
struct edge{
    int v,w;
};
struct node{
    int dis,u;
    bool operator>(const node &b)const{return dis>b.dis;}
};
bool vis[150007];
int dis[150007];
vector<edge> e[150007];
void dijkstra(int s){
    priority_queue<node,vector<node>,greater<node> > qu;
    memset(dis,0x7f,sizeof(dis));
    node p={0,s};
    dis[s]=0;
    qu.push(p);
    while(!qu.empty()){
        int u=qu.top().u;
        qu.pop();
        if(vis[u])continue;
        vis[u]=true;
        for(auto ed:e[u]){
            int v=ed.v;
            int w=ed.w;
            if(dis[v]>dis[u]+w){
                qu.push({dis[u]+w,v});
                //cout<<v<<' '<<u<<' '<<w<<endl;
                dis[v]=dis[u]+w;
            }
        }
    }
}
int danger[150007];
int vis1[150007];
struct poi{
    int id,num;
};
signed main(){
    
    cin>>n>>m>>k>>s;
    cin>>p>>q;
    queue<poi> qqqq;
    up(i,1,k){
        int x;
        cin>>x;
        danger[x]=2;
        qqqq.push((poi){x,0});
    }
    up(i,1,m){
        int u,v;
        cin>>u>>v;
        e[u].push_back((edge){v,0});
        e[v].push_back((edge){u,0});
    }
    while(!qqqq.empty()){
        poi u=qqqq.front();
        qqqq.pop();
        int id=u.id,num=u.num;
        if(num<s){
            for(auto ed:e[id]){
                if(!vis1[ed.v]){
                    danger[ed.v]=1;
                    qqqq.push({ed.v,num+1});
                    vis1[ed.v]=true;
                }
            }
        }
    }
//    up(i,1,n){
//        cout<<danger[i]<< " ";
//    }
//    cout<<endl;
    up(i,1,n){
        for(int j=0;j<e[i].size();j++){
            if(danger[i]==2){
                e[i][j].w=1e9;
                //cout<<i<<" "<<e[i][j].v<<" "<<e[i][j].w<<endl;
            }
            else if(danger[e[i][j].v]==1){
                e[i][j].w=q;
                //cout<<i<<" "<<e[i][j].v<<" "<<e[i][j].w<<endl;
            }
            else if(danger[e[i][j].v]==0){
                e[i][j].w=p;
                //cout<<i<<" "<<e[i][j].v<<" "<<e[i][j].w<<endl;
            }
            else{
                e[i][j].w=1e9;
                //cout<<i<<" "<<e[i][j].v<<" "<<e[i][j].w<<endl;
            }
        }
    }
    dijkstra(1);
    if(danger[n])dis[n]-=q;
    else dis[n]-=p;
    //for(int i=1;i<=n;i++)cout<<dis[i]<<' ';
    cout<<dis[n]<<endl;
}
                       
2023/8/25 16:25
加载中...