우리 고향 인 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가 작성한 스크립트를 기반으로이 작업에 대한 테스트를 제공 하고 있습니다 .
위의 스크립트를 사용할 수없는 사람을위한 테스트 및 예상 출력
용법: ./test [your program and its arguments]
보상
사양을 충족하고 모든 테스트를 통과 한 골프를 시도한 모든 답변은 저의 찬사를 얻습니다. 2012 년 1 월 26 일까지 최단 작업 답변이 수락됩니다.
답변
하스켈, 223207 자
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
답변
파이썬 (2.X), 382 369 358 338 323 318 자
모든 팁과 의견을 환영합니다!
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))
이 양식의 테스트를 통과해야합니다. stdin을 통한 피드 입력 (예 🙂 python shortestroute.py < test.txt
.
답변
C : 450 , 437 , 404 , 390 자
#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);
}