题解：CF2109D D/D/D

· · 题解

不难想到，一点从另一点能恰好走 n 条边，那么一定能恰好走 n+2\times k 条边。

那我们只需要判断奇偶性是否相同，并且最短路长度 \le 最大的能走的边数就行了。

分别维护最大的偶数和和最大的奇数和，以及 1 到每个点的最短奇数路径和最短偶数路径即可，前者很好维护，后者则用最短路。

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define INF 1e12
#define cc cin
#define oo cout
#define nm tie(0)
using namespace std;
const int N=2e5+5;
int t,n,m,k,sum;
int dis[N][2],b[N][2],a[N],c[N];
vector<int> ve[N];
signed main(){
//  freopen("1.out","r",stdin);
    //freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cc.nm;
    oo.nm;
    cin>>t;
    while(t--){
        cin>>n>>m>>k;
        for(int i=1;i<=n;i++) b[i][0]=b[i][1]=0,dis[i][0]=dis[i][1]=INF,ve[i].clear();
        int omax=0,jmax=0,ok=0,jk=0;
        a[1]=a[2]=c[1]=c[2]=0;
        sum=0;
        for(int i=1,x;i<=k;i++){
            cin>>x;
            sum+=x;
            if(x%2==1) a[++jk]=x;
            else c[++ok]=x;
        }
        for(int i=1,x,y;i<=m;i++){
            cin>>x>>y;
            ve[x].push_back(y);
            ve[y].push_back(x);
        }
        sort(a+1,a+jk+1,greater<int>{});
        sort(c+1,c+ok+1,greater<int>{});
        if(sum%2==0) omax=sum;
        else omax=sum-a[jk],jmax=sum;
        if(sum%2==0&&jk) jmax=sum-a[jk];
//      cout<<omax<<" "<<jmax<<"\n";
        dis[1][0]=0;
        queue<PII> q;
        q.push({1,0});
        while(!q.empty()){
            auto [u,v]=q.front();
            q.pop();
            if(b[u][v]) continue;
            b[u][v]=1;
            for(int x:ve[u]){
                if(dis[x][v^1]>dis[u][v]+1){
                    dis[x][v^1]=dis[u][v]+1;
                    q.push({x,v^1});
                }
            }
        }
        cout<<1;
        for(int i=2;i<=n;i++){
            if(dis[i][0]!=INF&&dis[i][0]<=omax){
                cout<<1;
            }
            else if(dis[i][1]!=INF&&dis[i][1]<=jmax){
                cout<<1;
            }
            else cout<<0;
        }
        cout<<"\n";
    } 
    return 0;
}
/*
2
2 1 1
1
1 2
2 1 1
2
1 2
*/