P1346 电车
P1346 电车
提交 20.68k
通过 6.92k
时间限制 1.00s
内存限制 125.00MB
标签
进入讨论版
相关讨论
推荐题目
题目描述
在一个神奇的小镇上有着一个特别的电车网络，它由一些路口和轨道组成，每个路口都连接着若干个轨道，每个轨道都通向一个路口（不排除有的观光轨道转一圈后返回路口的可能）。在每个路口，都有一个开关决定着出去的轨道，每个开关都有一个默认的状态，每辆电车行驶到路口之后，只能从开关所指向的轨道出去，如果电车司机想走另一个轨道，他就必须下车切换开关的状态。
为了行驶向目标地点，电车司机不得不经常下车来切换开关，于是，他们想请你写一个程序，计算一辆从路口 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 }
查看4道真题和解析
