우리 고향 인 Rhyl 은 일방 통행 교통 시스템을 갖추고있어 사람들이 가능한 한 오랫동안 목적지에서 멀리 떨어지도록 설계되었습니다. 당신이 그것을 시도하기로 선택한 경우, 당신의 임무는 그러한 교통 시스템을 통해 가장 짧은 경로를 제공하는 프로그램을 만드는 것입니다.

입력

입력은 on STDIN이며 다음과 같이 시작 및 끝 지점 목록과 빈 줄, 쿼리 목록이됩니다.

A B
B A
B C
C D
D C

A D
C A
B A

각 도로는 주어진 방향으로 만 이동할 수 있으므로 위의 예에서 도로 A-B는 양방향 거리 인 반면 B-C는 B에서 C까지의 일방 통행 거리입니다. C에서 B로 여행 금지되어 있습니다.

시작점과 끝점은 모두 대문자로 표시됩니다.

산출

출력은 주어진 시작 지점에서 수신 된 각 쿼리에 대해 지정된 끝 지점까지의 최단 경로 (방문한 지점 수로 측정) 여야합니다. 이러한 경로가 없으면 빈 줄을 출력하십시오. 최단 경로가 둘 이상 존재하는 경우, 모든 최단 경로를 사 전적으로 정렬 할 때 첫 번째 경로를 출력하십시오.

위의 예에서 출력은 다음과 같습니다.

A B C D

B A

테스트 스크립트

이전과 마찬가지로 Joey 와 Ventero가 작성한 스크립트를 기반으로이 작업에 대한 테스트를 제공 하고 있습니다 .

• 세게 때리다
• PowerShell

위의 스크립트를 사용할 수없는 사람을위한 테스트 및 예상 출력

• 일반 텍스트

용법: ./test [your program and its arguments]

보상

사양을 충족하고 모든 테스트를 통과 한 골프를 시도한 모든 답변은 저의 찬사를 얻습니다. 2012 년 1 월 26 일까지 최단 작업 답변이 수락됩니다.

답변

main=interact$unlines.f.break null.map words.lines
s%[f,t]=[[f]]#t where[]#_="";x#t|y@(_:_)<-[z|z<-x,last z==t]=unwords$minimum y|1<3=s&x#t
s&z=[x++[b]|x<-z,[a,b]<-s,last x==a,notElem b x];f(s,_:q)=map(s%)q

import os;u=str.split;l=u(os.read(0,1e9),'\n')
p,g,c=l.index(''),{},map;o=g.setdefault
def f(g,s,e,q=[]):q=q+[s];y=([],[q])[s==e];[c(y.append,f(g,n,e,q))for n in set(o(s,[]))-set(q)];return y
for k,v in c(u,l[:p]):o(k,[]);g[k]+=v
for w,e in c(u,l[p+1:]):h=sorted(f(g,w,e));print''if not h else' '.join(min(h,key=len))

#include<stdio.h>
#include <string.h>
r[99][99],p[99],q[99],m[99],i,j,x,y,s;
char t[9],e[9999];
F(k)
{
    m[k]^s?r[p[k]=q[i]][k]?m[q[j++]=k]=s:0:0;
    if(++k<99)F(k);
}
f()
{
    F(0);
    if(++i^j)f();
}
P(o)
{
    if(p[o])P(p[o]);
    *t=m[o]^s?0:o;
    strcat(e,t);
}
w()
{
    gets(t);
    r[*t][t[2]]=*t?w():0;
}
W()
{
    gets(t);
    x=*t,x?y=t[j=2],s=x+y*99,m[q[t[2]=i=p[x]=0]=x]=s,f(),P(y),strcat(e,"\n"),W():0;
}
main()
{
    w();
    W();
    puts(e);
}