求助
查看原帖
求助
1217682
xingtiankai2023楼主2024/6/3 22:58
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef long long ty;
const ty N = 200010,M = 400010,K = 200010;
ty n,m,k,s[K];
ty ver[M],nex[M],head[N],cnt = 0,d[N],f[N];//d[i]表示从1到i的最短路,f[i]表示从n到i的最短路
bool vis[N];
void add(ty x,ty y){ //添加一条边
    cnt++;
    ver[cnt] = y;
    nex[cnt] = head[x];
    head[x] = cnt;
}
struct cmp
{
    bool operator()(pair<ty,ty> &a,pair<ty,ty>&b){ //重载运算符
        return a.first>b.first;//小根堆
    }
};
priority_queue<pair<ty,ty>,vector<pair<ty,ty>>,cmp>q;
int main()
{
    cin >> n >> m >> k;
    for(ty i = 1;i <= k;i++){
        cin >> s[i];
    }
    sort(s+1,s+1+k); //排序
    k = unique(s+1,s+1+k)-s-1; //去重
    for(ty i = 1,x,y;i <= m;i++){
        cin >> x >> y;
        add(x,y);//添加无向边
        add(y,x);
    }
    memset(d,127,sizeof(d));
    d[1] = 0;
    q.push(make_pair(0,1));
    while(q.empty() == false){
        ty x = q.top().second;
        q.pop();
        if(vis[x]){
            continue;
        }
        vis[x] = true;
        for(ty i = head[x];i;i = nex[i]){
            ty y = ver[i];
            if(d[x]+1 < d[y]){
                d[y] = d[x]+1;
                q.push(make_pair(d[y],y));
            }
        }
    }
    memset(vis,0,sizeof(vis));
    memset(f,127,sizeof(f));
    f[n] = 0;
    q.push(make_pair(0,n));
    while(q.empty() == false){
        ty x = q.top().second;
        q.pop();
        if(vis[x]){
            continue;
        }
        vis[x] = true;
        for(ty i = head[x];i;i = nex[i]){
            ty y = ver[i];
            if(f[x]+1 < f[y]){
                f[y] = f[x]+1;
                q.push(make_pair(f[y],y));
            }
        }
    }
    ty ans = 0;
    for(ty i = 1;i < k;i++){ //枚举可能的值
        for(ty j = i+1;j <= k;j++){
            bool ok = true;
            ty x = s[i],y = s[j];
            for(ty i = head[x];i;i = nex[i]){
                if(ver[i] == y){
                    ok = false;
                    break;
                }
            }
            if(d[x] >= 0x3f3f3f3f || f[y] >= 0x3f3f3f3f){ //判断这两条路能不能走
                ok = false;
            }
            if(ok){
                ans = max(ans,d[x]+f[y]+1);
            }
            else{
                ans = max(ans,d[n]);
            }
        }
    }
    cout << ans;
    system("pause");
    return 0;
}

一直报错:UnexpectedResponse: got an unexpected response when requesting https://codeforces.com/enter: no RCPC values 为什么啊

2024/6/3 22:58
加载中...