| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 21783 | Accepted: 8107 |
Description
Input
Output
Sample Input
3 2 1 2 2 3 2 3 1 2 1 2
Sample Output
0
题意是输入n,a,b三个数，表示有n个点(1-n)，起点是a，终点是b，然后接下来有n行，每一行的第一个数m表示后面将会有m个数，输入结构是这样的，然后我再具体的解释一下。
3 2 1 3表示共有n个点，接下来有n行，2表示起点，1表示终点
2 2 3 第一个数2表示后面有2个数，因为这是第1行，所以后面两个数表示从1到2和从1到3的边
2 3 1 表示从2到3和从2到1的边
2 1 2 表示从3到1和从3到2的边
因为每个点都有开关，第一个点是不需要开开关的，但是之后的每一个都要开开关，意思是输入m后的第一条边是不需要开开关的，后面的2-m的边都是需要开开关的，比如样例的第二行，2 2 3就是1-2这条边不需要开开关，1-3这条边需要开开关。这道题最后问的就是从a点到b点，最少需要开多少个开关，题意很难读懂，懂了以后这道题就很简单了，把用不用开开关的作为边的权值，不用开开关的权值为0，用开开关的边权值为1，然后跑个dij就好了。
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <string> #include <map> #include <iomanip> #include <algorithm> #include <queue> #include <stack> #include <set> #include <vector> //const int maxn = 1e5+5; #define ll long long ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} #define inf 0x3f3f3f3f #define MAX INT_MAX #define FOR(i,a,b) for( int i = a;i <= b;++i) #define bug cout<<"--------------"<<endl using namespace std; int n,m,tot,A,B; int ver[11000],edge[11000],next[11000],head[11000],vis[11000],d[11000]; void add(int x,int y,int z) { ver[++tot] = y,edge[tot] = z,next[tot] = head[x],head[x] = tot; } void dijiestra() { priority_queue<pair<int,int> >que; memset(vis,0,sizeof(vis)); memset(d,inf,sizeof(d)); d[A] = 0; que.push(make_pair(0,A)); while(que.size()) { int x = que.top().second;que.pop(); if(vis[x] == 1) continue; vis[x] = 1; for(int i= head[x];i;i=next[i]) { int y = ver[i],z = edge[i]; if( d[y] > d[x] + z ) { d[y] = d[x] + z; que.push(make_pair(-d[y],y)); } } } } int main() { ios::sync_with_stdio(false); cin>>n>>A>>B; FOR(i,1,n) { int m,one; cin>>m>>one; add(i,one,0); FOR(j,2,m) { int two; cin>>two; add(i,two,1); } } dijiestra(); if(d[B] == inf) cout<<"-1"<<endl; else cout<<d[B]<<endl; }
原文：https://www.cnblogs.com/jrfr/p/11371112.html