社区讨论
P5767 为什么输出一样过不了
学术版参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lw1wq6r1
- 此快照首次捕获于
- 2024/05/11 17:31 2 年前
- 此快照最后确认于
- 2024/05/11 20:16 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
const int inf=1e10;
int n,m;
int f[505][505];
int t[505];
int dis[505];
char a;
int sum=0;
int vis[505];
int main(){
cin>>m>>n;
scanf("%c",&a);
memset(f,0x3f,sizeof(f));
for(int i=1;i<=m;i++){
int cnt=0,sum=0;
while(scanf("%c",&a)){
if(a=='\n') {
break;
}
else if(a==' '){
t[++cnt]=sum;
sum=0;
}
else{
sum=sum*10+a-48;
}
}
t[++cnt]=sum;
for(int j=1;j<=cnt;j++){
for(int k=j+1;k<=cnt;k++){
f[t[j]][t[k]]=1;
}
}
}
for(int i=1;i<=n;i++){
f[i][i]=1;
dis[i]=f[1][i];
}
vis[1]=1;
for(int i=1;i<n;i++){
int k=0,minn=INT_MAX;
for(int j=1;j<=n;j++){
if(!vis[j]&&dis[j]<minn){
minn=dis[j];
k=j;
}
}
if(k==0) break;
vis[k]=1;
for(int j=1;j<=n;j++)
if(!vis[j]&&dis[k]+f[k][j]<dis[j])
dis[j]=dis[k]+f[k][j];
}
if(dis[n]==inf) cout<<"NO";
else{
cout<<dis[n]-1;
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...