Autor da análise: tsebayoth
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1452
Resumo
O problema descreve um grafo (composto por 2 tipos diferentes de vértices, switches e signals) e algumas regras (as regras expressão a direção que você deve tomar no caminho entre 2 vértices). Dados 2 vértices origem e destino, você precisa devolver um caminho entre eles que satisfaça as regras.
Solução
O problema é simples, apenas o enunciado é confuso. O mais indicado é fazer um grafo implícito, observando a construção descrita no enunciado. A partir desse grafo, você roda um $DFS(origem, destino)$, sem se importar com as regras. Se você não encontrar um caminho, a resposta é "NOT POSSIBLE", caso contrário você precisa adequar o caminho encontrado, digamos $P=v_1,v_2,v_3,...,v_k$, às regras impostas. Para isso, para cada par $v_i,v_j \in P$, com $i<j$, ao qual existe uma regra "$v_i$ $v_j$ $s$" ($s \in \{+,-\}$), você roda $DFS(v_i,v_j,s)$, ou seja, procura um caminho de $v_i$ até $v_j$ tomando a direção "s", se tal caminho existe, você substitui o intervalo $v_i,v_{i+1},...v_j$ em P por esse novo caminho que você encontrou. Pronto, ao final você terá uma solução válida para o problema.
Discuta o problema
Joel .. coloque um exemplo de entrada e saída. De preferência um que mostre que existe um caminho entre s e t, só que não tem solução.
Alguém teve alguma dúvida?
Abraço,
wanderley