POJ1874 Tram

水題怡情...各ノードにはk本の出辺と1つの変換器があり、ノードに達するには変換器を起動して他の隣接点に行く必要があり、変換器の指す方向は現在の点で最初の点を指します.始点から終点までの最小起動変換器の回数を求める.
前は一度広く探せばいいと思っていましたが、よく考えてみると、各点に対応する変換器の方向のエッジを0にし、他の付与を1にして、単一ソースの最短パスを求めるだけでいいことがわかりました.
-1の場合を考えずに一度WAに貢献したので..ああ...
 

#include <iostream>
using namespace std;
const int MAXN = 200;
const int MAXM = MAXN*MAXN;
struct node
{
       int v, w, next;       
}mapp[MAXM];
int id;
int head[MAXN];
void init()
{
     id = 0;
     memset(head, -1, sizeof(head));     
}

void addedge(int u, int v, int w)
{
     mapp[id].v = v, mapp[id].w = w, mapp[id].next = head[u], head[u] = id ++;     
}
bool inque[MAXN];
int dist[MAXN];
int Que[10*MAXM];
const int inf = 1 << 30;
void SPFA(int s,int n)
{
     for (int i = 1; i <= n; i ++){
         inque[i] = false;
         dist[i] = inf;    
     }
     dist[s] = 0;
     inque[s] = true;
     int rear, front;
     rear = front = 0;
     Que[rear ++] = s;
     while (front < rear){
           int pre = Que[front ++];
           inque[pre] = false;
           for (int i = head[pre]; i != -1; i = mapp[i].next){
               int v = mapp[i].v;
               if (dist[v] > dist[pre] + mapp[i].w){
                   dist[v] = dist[pre] + mapp[i].w;
                   if (!inque[v]){
                      inque[v] = true;
                      Que[rear ++] = v;               
                   }
               }    
           }
     }
}
int main()
{
    int n, s, t;
    while (scanf("%d%d%d", &n, &s, &t) != EOF){
          init();
          for (int i = 1; i <= n; i ++){
              int a, b, c;
              scanf("%d", &a);
              int nc = 0;
              while (a --){
                    scanf("%d", &b);
                    if (!nc)addedge(i, b, 0);
                    else addedge(i, b, 1);
                    nc ++;
              }      
          }     
          SPFA(s, n);
          if (dist[t] == inf){
             printf("-1
");            
          }
          else
          printf("%d
", dist[t]);
    }
    return 0;    
}