NOIP2014 TG T5 寻找道路
感觉自己弱爆了是吧,还在做去年的NOIP的T5,真心不知道当年用的是什么傻B算法反正那时就10分,完全代表窝Day2报废了对吧
然后终于A了
感觉自己拖延症真心讨厌啊。。。
拖了这么久才来A这道出了考场问了大神就知道算法的题
两遍BFS不用说,当时不会邻接表,现在终于会了。。。(表示不怎么理解,就是把代码背了,求大神教导%%%)
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <queue> #include <string> #include <algorithm> #define NN 10100 #define MM 200100 using namespace std; queue <int> que; queue <int> dis; int ne1[MM],ne2[MM],head1[MM],head2[MM],v1[MM],v2[MM]; int tota,totb; int x,y,s,t,n,m; bool f[NN],used[NN]; void Build(int xx,int yy) { ne1[++tota]=head1[xx]; head1[xx]=tota; v1[tota]=yy; ne2[++totb]=head2[yy]; head2[yy]=totb; v2[totb]=xx; } void BFSa() { while (!que.empty()) que.pop(); que.push(t); f[t] = 0; while (!que.empty()) { int h=que.front(); que.pop(); for (int i=head2[h];i;i=ne2[i]) { if (f[v2[i]]) { f[v2[i]]=0; que.push(v2[i]); } } } return; } bool check(int xx) { for (int i=head1[xx];i;i=ne1[i]) if (f[v1[i]]) return 0; return 1; } void BFSb() { while (!que.empty()) que.pop(); while (!dis.empty()) dis.pop(); que.push(s); dis.push(0); used[s]=1; while (!que.empty()) { int h=que.front(); que.pop(); int d=dis.front(); dis.pop(); if (!check(h)) continue; for (int i=head1[h];i;i=ne1[i]) { if (!used[v1[i]]) { if (v1[i]==t) { printf("%d\n",d+1); return; } que.push(v1[i]); used[v1[i]]=1; dis.push(d+1); } } } puts("-1"); return; } int main() { scanf("%d%d",&n,&m); tota=totb=0; for (int i=1;i<=m;++i) { scanf("%d%d",&x,&y); if (x!=y) Build(x,y); } scanf("%d%d",&s,&t); memset(f,1,sizeof(f)); BFSa(); memset(used,0,sizeof(used)); if (f[s]) { puts("-1"); return 0; } BFSb(); return 0; }
不管怎么样,A题总是一件欢乐的事对吧~~