洛谷 P1346 电车——dijstra

上一波题目 https://www.luogu.org/problem/P1346

是道水题 路口一开始对着的那条路权值为0 其余路权值为1 然后跑一遍最短路就好了

qwq

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<cmath>

#define inf 1e9

using namespace std;

const int M=1e5+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,Ts,Td;

int first[M],cnt;

struct node{int to,next,w;}e[*M];

void ins(int x,int y,int w){e[++cnt]=(node){y,first[x],w}; first[x]=cnt;}

struct qwq{

    int id,d;

    bool operator<(const qwq&x)const{return x.d<d;}

};

int dis[M];

priority_queue<qwq>q;

void dj(){

    for(int i=;i<=n;i++) dis[i]=inf;

    dis[Ts]=; q.push((qwq){Ts,dis[Ts]});

    while(!q.empty()){

        qwq x=q.top(); q.pop();

        if(x.d<dis[x.id]) continue;

        for(int i=first[x.id];i;i=e[i].next){

            int now=e[i].to;

            if(dis[now]>dis[x.id]+e[i].w){

                dis[now]=dis[x.id]+e[i].w;

                q.push((qwq){now,dis[now]});

            }

        }

    }

}

int main(){

    int k,x;

    n=read(); Ts=read(); Td=read();

    for(int i=;i<=n;i++){

        k=read();

        for(int j=;j<=k;j++){

            x=read();

            if(j==) ins(i,x,);

            else ins(i,x,);

        }

    }

    dj();

    if(dis[Td]==inf) puts("-1");

    else printf("%d\n",dis[Td]);

    return ;

}