记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 8ms 560.0 KiB
#2 Accepted 1ms 1.008 MiB
#3 Accepted 2ms 344.0 KiB
#4 Accepted 2ms 344.0 KiB
#5 Accepted 2ms 440.0 KiB
#6 Accepted 1ms 468.0 KiB
#7 Accepted 38ms 692.0 KiB
#8 Accepted 8ms 1.973 MiB
#9 Accepted 3ms 856.0 KiB
#10 Accepted 37ms 6.594 MiB

代码

#include<bits/stdc++.h>
using namespace std; 
const int maxn=10010,maxm=200010,inf=0x3f3f3f3f;
int n,m,cnt1,cnt2,s,t;
int head1[maxn],dis1[maxn],dis2[maxn],head2[maxn],mark[maxn],vis[maxn];
struct edge{
	int from,to,v,next;
}e1[maxm],e2[maxm];

inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=((x<<1)+(x<<3))+c-'0';
		c=getchar();
	}
	return x*f;
}

inline void add1(int a,int b,int c){
	e1[++cnt1].from=a;
	e1[cnt1].to=b;
	e1[cnt1].v=c;
	e1[cnt1].next=head1[a];
	head1[a]=cnt1;
}

inline void add2(int a,int b,int c){
	e2[++cnt2].from=a;
	e2[cnt2].to=b;
	e2[cnt2].v=c;
	e2[cnt2].next=head2[a];
	head2[a]=cnt2;
}

inline void Init(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int x,y;
		x=read(),y=read();
		add1(x,y,1),add2(y,x,1);
	}
	s=read(),t=read();
}

inline void markit(){
	for(int i=1;i<=n;i++){
		if(dis2[i]==inf){
			mark[i]=1;
			for(int j=head2[i];j;j=e2[j].next)
				mark[e2[j].to]=1;
		}
	}
}

inline void spfa1(int s){
	queue<int> q;
	memset(vis,0,sizeof(vis));
	memset(dis1,0x3f,sizeof(dis1));
	q.push(s);
	dis1[s]=0;
	vis[s]=1;
	while(q.size()){
		int x=q.front();q.pop();vis[x]=0;
		for(int i=head1[x];i;i=e1[i].next){
			int y=e1[i].to;
			if(mark[y])continue;
			if(dis1[y]>dis1[x]+e1[i].v){
				dis1[y]=dis1[x]+e1[i].v;
				if(!vis[y]){
					vis[y]=1;
					q.push(y);
				}
			}
		}
	}
}

inline void spfa2(int s){
	queue<int> q;
	memset(vis,0,sizeof(vis));
	memset(dis2,0x3f,sizeof(dis2));
	q.push(s);
	dis2[s]=0;
	vis[s]=1;
	while(q.size()){
		int x=q.front();q.pop();vis[x]=0;
		for(int i=head2[x];i;i=e2[i].next){
			int y=e2[i].to;
			if(dis2[y]>dis2[x]+e2[i].v){
				dis2[y]=dis2[x]+e2[i].v;
				if(!vis[y]){
					vis[y]=1;
					q.push(y);
				}
			}
		}
	}
}

inline void Work(){
	spfa2(t);		
	markit();
	if(mark[s]){
		cout<<-1<<endl;
	}
	else{
		spfa1(s);
		cout<<dis1[t]<<endl;
	}
}

int main(){
	Init();
	Work();
	return 0;
}

信息

递交者
类型
递交
题目
P1025 寻找道路
比赛
随机真题赛第三轮(xhy&lfy讲题)
题目数据
下载
语言
C++
递交时间
2019-11-12 14:54:45
评测时间
2019-11-12 14:54:45
评测机
分数
100
总耗时
107ms
峰值内存
6.594 MiB