别的OJ过了,测试数据也完全一样,怎么还是wa?
查看原帖
别的OJ过了,测试数据也完全一样,怎么还是wa?
434015
Calanosay楼主2021/5/3 13:50

测试了一下洛谷给出的数据,输出也完全一致,但是显示WA?

#include<bits/stdc++.h>
using namespace std;
const int inf=1e6;
const int maxn=505;
const int maxm=1e5;
int dis[maxn],vis[maxn];
int head[maxn],w[maxm],v[maxm],nex[maxm],cnt;
void add(int x,int y){
    v[++cnt]=y;
    nex[cnt]=head[x];
    head[x]=cnt;
}
int main(){
    vector<int> tem,g[maxn];
    int n,m;
    cin>>m>>n;
    getchar();
    for(int i=2;i<=n;i++)   dis[i]=inf;
    for(int i=1;i<=m;i++) {
        string s;
        getline(cin,s);
        stringstream ss;
        ss<<s;
        int p;
        while (ss>>p){
            tem.push_back(p);
        }
        for(int i=0;i<tem.size();i++)
            for(int j=i+1;j<tem.size();j++)
                g[tem[i]].push_back(tem[j]);
        tem.clear();
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<g[i].size();j++)
            add(i,g[i][j]);
    queue<int> q;
    dis[1]=0;
    vis[1]=1;
    q.push(1);
    while(!q.empty()){
        int node=q.front();q.pop();vis[node]=0;
        for(int i=head[node];i;i=nex[i]){
            int to=v[i];
            if(dis[to]>dis[node]+1){
                dis[to]=dis[node]+1;
                if(!vis[to]){
                    q.push(to);
                    vis[to]=1;
                }
            }
        }
    }
    if(dis[n]!=inf) cout<<dis[n]-1;
    else    puts("NO");
}

2021/5/3 13:50
加载中...