30分求助大佬
  • 板块P1346 电车
  • 楼主CandZgamer
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/18 18:14
  • 上次更新2023/11/18 19:30:36
查看原帖
30分求助大佬
669678
CandZgamer楼主2023/11/18 18:14
#include<bits/stdc++.h>
using namespace std;
const int maxmax=1e9;
int d[105][105],f[105],l[105],n,A,B;
void dijk(int s){
	for(int i=1;i<=n;i++){
		l[i]=d[s][i];
		f[i]=0;
	}
	f[s]=1;
	for(int i=1;i<n;i++){
		int dmin=maxmax,v=s;
		for(int j=1;j<=n;j++){
			if(f[j]==0&&l[j]<dmin){
				dmin=l[j];
				v=j;
			}
		}
		if(dmin==maxmax){
			break;
		}
		f[v]=1;
		for(int j=1;j<=n;j++){
			if(f[j]==0&&l[j]<dmin){
				if(l[v]+d[v][j]<l[j]){
					l[j]=l[v]+d[v][j];
				}
			}
		}
	}
}
int main(){
	cin>>n>>A>>B;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i!=j){
				d[i][j]=maxmax;
			}else{
				d[i][j]=0;
			}
		}
	}
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x;
		for(int j=1;j<=x;j++){
			cin>>y;
			if(j==1){
				d[i][j]=0;
			}else{
				d[i][j]=1;
			}
		}
	}
	dijk(A);
	if(l[B]==maxmax){
		cout<<"-1";
		return 0;
	}
	cout<<l[B];
	return 0;
}
2023/11/18 18:14
加载中...