P1346 电车

提交 20.68k
通过 6.92k
时间限制 1.00s
内存限制 125.00MB
题目提供者 yeszy
历史分数100

提交记录

查看题解

标签

 
查看算法标签
进入讨论版

相关讨论

 
查看讨论

推荐题目

 
查看推荐
 

展开

题目描述

在一个神奇的小镇上有着一个特别的电车网络，它由一些路口和轨道组成，每个路口都连接着若干个轨道，每个轨道都通向一个路口（不排除有的观光轨道转一圈后返回路口的可能）。在每个路口，都有一个开关决定着出去的轨道，每个开关都有一个默认的状态，每辆电车行驶到路口之后，只能从开关所指向的轨道出去，如果电车司机想走另一个轨道，他就必须下车切换开关的状态。

为了行驶向目标地点，电车司机不得不经常下车来切换开关，于是，他们想请你写一个程序，计算一辆从路口 AAA 到路口 BBB 最少需要下车切换几次开关。

输入格式

第一行有 333 个整数 N,A,BN,A,BN,A,B（2≤N≤100,1≤A,B≤N2 \leq N \leq 100, 1 \leq A,B \leq N2≤N≤100,1≤A,B≤N），分别表示路口的数量，和电车的起点，终点。

接下来有 NNN 行，每行的开头有一个数字 KiK_iKi​（0≤Ki≤N−10 \leq K_i \leq N-10≤Ki​≤N−1），表示这个路口与 KiK_iKi​ 条轨道相连，接下来有 KiK_iKi​ 个数字表示每条轨道所通向的路口，开关默认指向第一个数字表示的轨道。

输出格式

输出文件只有一个数字，表示从 AAA 到 BBB 所需的最少的切换开关次数，若无法从 AAA 前往 BBB，输出 −1-1−1。

输入输出样例

输入 #1 
3 2 1
2 2 3
2 3 1
2 1 2
输出 #1 
0

思路
　　对于第一条边连0，之后的边连1跑dij
　　由于数据比较水，第一发看错题交了发dfs暴力也有50P
CODE
  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 template<class T>inline void read(T &res)
 10 {
 11     char c;T flag=1;
 12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 14 }
 15 
 16 namespace _buff {
 17     const size_t BUFF = 1 << 19;
 18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 19     char getc() {
 20         if (ib == ie) {
 21             ib = ibuf;
 22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 23         }
 24         return ib == ie ? -1 : *ib++;
 25     }
 26 }
 27 
 28 int qread() {
 29     using namespace _buff;
 30     int ret = 0;
 31     bool pos = true;
 32     char c = getc();
 33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 34         assert(~c);
 35     }
 36     if (c == '-') {
 37         pos = false;
 38         c = getc();
 39     }
 40     for (; c >= '0' && c <= '9'; c = getc()) {
 41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 42     }
 43     return pos ? ret : -ret;
 44 }
 45 
 46 const int maxn = 1e5 + 7;
 47 const int inf  = 0x3f3f3f3f;
 48 
 49 int head[maxn << 1], edge[maxn << 1], w[maxn << 1], nxt[maxn << 1];
 50 int cnt;
 51 
 52 inline void BuildGraph (int u, int v, int c) {
 53     cnt++;
 54     edge[cnt] = v;
 55     nxt[cnt]  = head[u];
 56     w[cnt] = c;
 57     head[u] = cnt;
 58 }
 59 
 60 struct node {
 61     int u,v;
 62     bool operator <(const node &t) const {
 63         return u > t.u;
 64     }
 65 };
 66 
 67 int n,m,s,t;
 68 int dis[maxn];
 69 
 70 priority_queue < node > q;
 71 
 72 void dijkstra(int s) {
 73     for (int i = 1; i <= n; ++i) {
 74         dis[i] = inf;
 75     }
 76     dis[s] = 0;
 77     node temp;
 78     temp.u = 0;
 79     temp.v = s;
 80     q.push(temp);
 81     while(!q.empty()) {
 82         int u = q.top().v;
 83         int d = q.top().u;
 84         q.pop();
 85         if(d != dis[u]) continue;
 86         for (int i = head[u]; i; i = nxt[i]) {
 87             int v = edge[i];
 88             int c = w[i];
 89             if(dis[v] > dis[u] + c) {
 90                 dis[v] = dis[u] + c;
 91                 node p;
 92                 p.u = dis[v], p.v = v;
 93                 q.push(p);
 94             }
 95         }
 96     }
 97 }
 98 
 99 int main()
100 {
101     scanf("%d %d %d",&n, &s, &t);
102     for ( int i = 1; i <= n; ++i ) {
103         int k;
104         read(k);
105         for ( int j = 1; j <= k; ++j ) {
106             int x;
107             read(x);
108             if(j == 1) {
109                 BuildGraph(i, x, 0);
110             }
111             else {
112                 BuildGraph(i, x, 1);
113             }
114         }
115     }
116     dijkstra(s);
117     if(dis[t] != inf) printf("%d\n",dis[t]);
118     else {
119         puts("-1");
120     }
121     return 0;
122 }
View Code