10pts求助
查看原帖
10pts求助
566903
福明o7楼主2022/7/28 23:34
#include<bits/stdc++.h>
using namespace std;
const int MAXN=505;
bool vis[MAXN];
int dis[MAXN],g[MAXN][MAXN];
int a[MAXN];
int m,n;
/*
struct node{
	int to;
	int from;
	int w;
	int nxt;
};链式前向星是啥?(划掉) 
	邻接矩阵在允许范围内真好 
*/
void Dijkstra(){
	int k;
	int u;
	vis[1]=1;
	for(int i=1;i<=n;i++){
		if(i==1){
			dis[i]=0;
		}
		else{
			dis[i]=g[1][i];
		}
	}
	for(int i=1;i<=n-2;i++){
		u=1e9;
		for(int j=1;j<=n;j++){
			if(dis[j]<u&&!vis[j]){
				u=dis[j];
				k=j;
			}
		}
		if(u==1e9){
			break;//没更新直接跳了 
		}
		vis[k]=1;
		for(int j=1;j<=n;j++){
			if(dis[k]+g[k][j]<dis[j]){
				dis[j]=dis[k]+g[k][j];
			}
		}
	}
	return;
}
int main(){
	scanf("%d %d",&m,&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			g[i][j]=1e9;
		}
	}
	for(int i=1;i<=m;i++){
		memset(a,0,sizeof(a));
		int x,to=0;
		while(scanf("%d",&x)!=EOF){
			a[++to]=x;
		}
		for(int j=1;j<n;j++){
			for(int k=j+1;k<=n;k++){
				g[a[j]][a[k]]=1;
			}
		}
	}
	Dijkstra();
	if(dis[n]>=1e9){
		puts("NO");
	} 
	else{
		printf("%d\n",dis[n]-1);
	}
	return 0;
}

一直在10pts~30pts之间浮动(改输入),主体找不到错,求助

2022/7/28 23:34
加载中...