记录编号	570869	评测结果	AAAAAAAAAA
题目名称	[CSP JX2019PJ]道路拆除(民间数据)	最终得分	100
用户昵称	Lesater	是否通过	通过
代码语言	C++	运行时间	2.327 s
提交时间	2022-04-21 14:50:23	内存使用	0.00 MiB

#include<bits/stdc++.h>
using namespace std;
struct Node{
    vector<int> to;
};
Node c[35001];
int n,m,l1,t1,l2,t2;
int x[3][35001];
void asd(int p,int t,int nub)
{
    if(t>x[nub][p]) return;    
    x[nub][p]=t;
    for(int i=0;i<c[p].to.size();++i)
    {
        asd(c[p].to[i],t+1,nub);
    }
    return;
}
int main()
{
    freopen("cspjx2019pj_dismantle.in","r",stdin);
    freopen("cspjx2019pj_dismantle.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
       for(int j=0;j<3;++j)
       x[j][i]=INT_MAX;
    for(int i=1;i<=m;++i)
    {
        int a,b;
        cin>>a>>b;
        c[a].to.push_back(b);
        c[b].to.push_back(a);
    }
    cin>>l1>>t1>>l2>>t2;
    asd(1,0,0);
    asd(l1,0,1);
    asd(l2,0,2);
    int maxn=INT_MAX;
    for(int i=1;i<=n;++i)
    {
            if(x[0][i]!=INT_MAX&&x[1][i]!=INT_MAX&&x[2][i]!=INT_MAX&&(x[0][i]+x[1][i]<=t1)&&(x[0][i]+x[2][i]<=t2))
            maxn=min(maxn,x[0][i]+x[1][i]+x[2][i]);
    }
    if(maxn==INT_MAX) cout<<-1;
    else cout<<m-maxn;
    return 0;
}