POJ 1847 Tram(详细题意+dijkstra)

    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的边

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define inf 0x3f3f3f3f
#define maxn 505
using namespace std;
struct Node{
  int to,w,next;
  bool operator < (const Node &a) const {
    return a.w < w;
  }
}Edge[maxn * maxn],Now,Next;
int head[maxn * maxn],num;
int n,m,a,b;

void init(){
  memset(head,-1,sizeof(head));
  num = 0;
}

void add(int u,int v,int w){
  Edge[num].to = v;
  Edge[num].w = w;
  Edge[num].next = head[u];
  head[u] = num ++;
}

void dijkstra(){
  int dist[maxn];
  bool vis[maxn];
  memset(dist,inf,sizeof(dist));
  memset(vis,false,sizeof(vis));
  dist[a] = 0;
  Now.to = a;
  priority_queue<Node> q;
  q.push(Now);
  while(!q.empty()){
    Now = q.top();
    q.pop();
    int ans = Now.to;
    if(vis[ans]) continue;
    vis[ans] = true;
    for(int i=head[ans];i!=-1;i=Edge[i].next){
      int u = Edge[i].to;
      if(!vis[u] && dist[u] > dist[ans] + Edge[i].w){
        dist[u] = dist[ans] + Edge[i].w;
        Next.to = u;
        Next.w = dist[u];
        q.push(Next);
      }
    }
  }
  printf("%d\n",dist[b] == inf ? -1 : dist[b]);
}

int main()
{
  scanf("%d%d%d",&n,&a,&b);
  init();
  for(int i=1;i<=n;i++){
    scanf("%d",&m);
    int v;
    scanf("%d",&v);
    add(i, v, 0);
    for(int j=1;j<m;j++){
      scanf("%d",&v);
      add(i, v, 1);
    }
  }
  dijkstra();
  return 0;
}