题意：
朋友圈，如果彼此都认为对方是朋友帮忙就无花费，否则花费为1，如果是一个环也认为彼此是朋友。
思路：
强联通分量缩点，重新造边，跑最短路。
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <queue> #include <vector> using namespace std; const int MAXN =100000 ; const int MAXM =100000 ; using namespace std; const int maxn=100005; struct node ///优先队列， 在距离相同时选最小花费 { int v,w,dis; node(int _v=0,int _w=0,int _dis=0):v(_v),w(_w),dis(_dis){} bool operator <(const node &r)const { if(dis!=r.dis) return dis>r.dis; else return w>r.w; } }; vector<node> vec[maxn];///存边 struct Edge { int to,next; }edge[MAXM]; int head[MAXN],tot; int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN]; int Index,top; int scc; int vis[maxn]; int dis[maxn];///存最短路径 const int inf=0x3f3f3f3f; bool Instack[MAXN]; void addedge(int u,int v) { edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++; } void dijk(int st,int n) { for(int i=1;i<=n;i++) { vis[i]=0; dis[i]=inf; } priority_queue<node> q; dis[st]=0; q.push(node(st,0,0)); node tmp; while(!q.empty()) { tmp=q.top(); q.pop(); int u=tmp.v; if(vis[u]) continue; vis[u]=1; for(int i=0;i<vec[u].size();i++) { int v=vec[u][i].v; int cost=vec[u][i].w; if(!vis[v]&&dis[v]>=dis[u]+cost) { dis[v]=dis[u]+cost; q.push(node( v,cost,dis[v])); } } } if(dis[Belong[n]]!=inf) printf("%d\n",dis[Belong[n]]); else printf("-1\n"); } void Tarjan(int u) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; for(int i = head[u];i != -1;i = edge[i].next) { v = edge[i].to; if(!DFN[v]) { Tarjan(v); if(Low[u] > Low[v]) Low[u] = Low[v]; } else if(Instack[v] && Low[u] > DFN[v]) Low[u] = DFN[v]; } if(Low[u] == DFN[u]) { scc++; do { v = Stack[--top]; Belong[v] = scc; Instack[v] = false; } while( v!= u ); } } int in[MAXN],out[MAXN]; void solve(int N) { for(int i=1;i<=N;i++) vec[i].clear(); memset(DFN,0,sizeof(DFN)); memset(Instack,false,sizeof(Instack)); Index = scc = top = 0; for(int i = 1;i <= N;i++) if(!DFN[i]) Tarjan(i); for(int u = 1;u <= N;u++) { for(int i = head[u];i != -1;i = edge[i].next) { int v = edge[i].to; if(Belong[u] != Belong[v]) { vec[Belong[u]].push_back(node(Belong[v],1,0)); } } } /* for(int i=1;i<=scc;i++) { for(int j=0;j<vec[i].size();j++) { printf("%d--%d\n ",i,vec[i][j]); } }*/ dijk(Belong[1],N); } void init() { tot = 0; memset(head,-1,sizeof(head)); } int main() { int n,m; int v; int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); init(); int u,v; for(int i = 1;i <= m;i++) { scanf("%d%d",&u,&v); u++,v++; addedge(u,v); } solve(n); } return 0; }
