萌新刚学图论,求助70分
  • 板块P1346 电车
  • 楼主⚡小林子⚡海棠喵
  • 当前回复10
  • 已保存回复10
  • 发布时间2020/7/6 11:28
  • 上次更新2023/11/6 23:34:41
查看原帖
萌新刚学图论,求助70分
100910
⚡小林子⚡海棠喵楼主2020/7/6 11:28

record

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,a,b,k,x,dis[201];
bool vis[201];
struct Node{
	int v,d;
	bool operator < (const Node &rhs) const {
		return d>rhs.d;
	}
}vex; 
vector<Node>G[201];
void dijkstra(int x){
	priority_queue<Node>pq; 
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	dis[x]=0;
	vex.d=0;vex.v=x;
	pq.push(vex);
	while(!pq.empty()){
		vex=pq.top();pq.pop();
		int v=vex.v,d=vex.d;
		if(vis[v]) continue;
		vis[v]=1;
		for(int i=0;i<G[v].size();i++){
			int j=G[v][i].v;
			if(!vis[j]&&dis[v]+G[v][i].d<dis[j]){
				dis[j]=dis[v]+G[v][i].d;
				vex.v=j;vex.d=dis[j];
				pq.push(vex);
			}
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<=n;i++){
		scanf("%d",&k);
		if(!k) continue;
		scanf("%d",&x);
		vex.v=x;vex.d=0;
		G[i].push_back(vex);
		for(int i=1;i<k;i++){
			scanf("%d",&x);
			vex.v=x;vex.d=1;
			G[i].push_back(vex);
		}
	}
	dijkstra(a);
	if(dis[b]==0x3f3f3f3f)
		puts("-1");
	else 
		printf("%d",dis[b]); 
	return 0;
}
2020/7/6 11:28
加载中...