14176: 【原4176】失败铁路网

题目描述

author: 失败原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4176

题目描述

一条失败的铁路网由若干站点和轨道构成。每个站点与其他若干个站点相连。每个站点有一个开关，会将驶入站点的失败列车引导到某个相连的站点。每个站点都有一个初始指向。现在失败要乘坐失败列车从起点到达终点。但是由于这个铁路网实在太失败了，所以沿着各个站点的初始指向，未必能到达目的地。失败需要调整铁路网中某些站点的指向才能到达终点。

请问失败至少需要调整几个站点的指向？

输入格式

第一行包含三个正整数n, a, b。表示站点数量、起点、终点

接下来N行表示，每行第一个数字Ki表示与这个站点相连的站点的数量，接下来的Ki个数字分别表示与该站点相连的站点编号。默认指向第一个数字表示的站点。

输出格式

一个整数，表示从a到b最少需要调整几个站点的指向。如果无法从a到达b，输出-1

样例输入

样例输出

数据范围

2<=N<=1000, 1<=A,B<=N

WashSwang's solution

#include <iostream>
#include <cstring>
using namespace std;
struct node{
    int val,p;
} h[1001],cur;
int n,nxt,a,b,len,pos[1001],way[1001][1001],k[1001],ans[1001];
void minheapify(int x){
    int smallest=x,l,r;
    while (true) {
        l=x<<1;
        r=l+1;
        if (l <= len && h[l].val < h[x].val) smallest = l;
        if (r <= len && h[r].val < h[smallest].val) smallest = r;
        if (smallest != x) {
            swap(pos[h[smallest].p],pos[h[x].p]);
            swap(h[smallest],h[x]);
            x = smallest;
        }
        else break;
    }
}
node pop(){
    node ret=h[1];
    pos[ret.p]=0;
    h[1]=h[len--];
    pos[h[1].p]=1;
    minheapify(1);
    return ret;
}
void insert(int val,int p){
    int i=++len;
    pos[p]=len;
    h[len].val=val;
    h[len].p=p;
    while (i>1 && h[i>>1].val>h[i].val)
    {
        swap(pos[h[i].p],pos[h[i>>1].p]);
        swap(h[i],h[i>>1]);
        i>>=1;
    }
}

void modify(int val,int p){
    h[p].val=val;
    int i=p;
    while (i>1 && h[i>>1].val>h[i].val)
    {
        swap(pos[h[i].p],pos[h[i>>1].p]);
        swap(h[i],h[i>>1]);
        i>>=1;
    }
}

int main() {
    scanf("%d%d%d",&n,&a,&b);
    for (int i=1;i<=n;++i){
        scanf("%d",&k[i]);
        for (int j=0;j<k[i];++j)
            scanf("%d",&way[i][j]);
        ans[i]=-1;
    }
    insert(0,a);
    while (len>0){
        cur=pop();
        ans[cur.p]=cur.val;
        if (k[cur.p]>0) {
            nxt=way[cur.p][0];
            if (pos[nxt]) {
                if (cur.val < h[nxt].val) modify(cur.val, pos[nxt]);
            }
            else if (ans[nxt]==-1||cur.val+1<ans[nxt]) insert(cur.val,nxt);
            for (int i=1;i<k[cur.p];++i)
            {
                nxt=way[cur.p][i];
                if (pos[nxt]) {
                    if (cur.val + 1 < h[nxt].val) modify(cur.val + 1, pos[nxt]);
                }
                else if (ans[nxt]==-1||cur.val+1<ans[nxt]) insert(cur.val+1,nxt);
            }
        }
    }
    printf("%d",ans[b]);
    return 0;
}