p1346 60分求改 QaQ
查看原帖
p1346 60分求改 QaQ
1013872
ShenYuZe18991811806楼主2024/4/15 21:09

求改QaQ

#include<bits/stdc++.h> 
using namespace std;
struct road{
	int e,l;
};
vector<road>g[1000];
int num,st,en;
int vis[1000],dist[1000],now;
queue<int>q;
void spfa(){
	for(int i=0;i<=num;i++){
		dist[i]=1e9;
	}
	q.push(st);
	vis[st]=1;
	dist[st]=0;
	while(!q.empty()){
		now=q.front();
		q.pop();
		vis[now]=0;
		for(int i=0;i<g[now].size();i++){
			road to=g[now][i];
			if(dist[to.e]>dist[now]+to.l){
				dist[to.e]=dist[now]+to.l;
				if(vis[to.e]==0){
					vis[to.e]=1;
					q.push(to.e);
				}
			}
		}
	}
}
int main() {
    cin>>num>>st>>en;
    int to_num;
    int end;
    for(int i=1;i<=num;i++){
    	cin>>to_num;
    	cin>>end;
    	g[i].push_back({end,0});
    	for(int j=1;j<to_num;j++){
    		cin>>end;
    		g[j].push_back({end,1});
		}
	}
	spfa();
	if(dist[en]==1e9){
		cout<<"-1\n";
		return 0;
	}
	cout<<dist[en];
}
2024/4/15 21:09
加载中...