WA 七个点求调悬关
查看原帖
WA 七个点求调悬关
777756
UFOI楼主2023/11/4 16:18
#include<bits/stdc++.h>
using namespace std;
int n,m,k,u,v,w,s,cnt,head[400001],dis[400001];
bool vis[400001];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
struct node{
    int to,next,dis;
}e[800001];
void add(int u,int v,int w){
    cnt++;
    e[cnt].next=head[u];
    e[cnt].to=v;
    e[cnt].dis=w;
    head[u]=cnt;
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        if(w==0){
            add(u+n,v+n,1);
            add(v+n,u+n,1);
        }
        else{
            add(u,v,1);
            add(v,u,1);
        }
    }
    for(int i=1;i<=k;i++){
        cin>>s;
        add(s,s+n,0);
        add(s+n,s,0);
    }
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    q.push({1,0});
    while(q.size()){
        pair<int,int> tmp=q.top();
        q.pop();
        int x=tmp.first;
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(dis[y]>dis[x]+e[i].dis){
                dis[y]=dis[x]+e[i].dis;
                if(!vis[y]) q.push({y,dis[y]});
            }
        }
    }
    if(min(dis[n],dis[n*2])==0x3f3f3f3f) puts("-1");
    else cout<<min(dis[n],dis[n*2]);
}

https://atcoder.jp/contests/abc277/submissions/47201016

2023/11/4 16:18
加载中...