Python-сообщество

# coding: windows-1251
import itertools

class Map:
    def __init__( self, N, roads, start_state ):
        # Строим индексы соседних узлов
        index = [ set() for n in range(N) ]

        for n1, n2 in roads:
            index[n1].add( n2 )
            index[n2].add( n1 )

        self.index = index

        # Уже обработанные состояния
        self.old_states = dict( [[start_state,None]] )

        # Возможные состояния на текущем шаге
        self.last_states = [ start_state ]

    def states_gen( self, state ):
        args = [ self.index[n] for n in state ]
        return ( s for s in itertools.product( *args ) if s not in self.old_states )

    def one_step( self ):
        print "Next step, last_states: %d, old_states: %d" % ( len( self.last_states ), len( self.old_states ) )

        new_states = []

        for state in self.last_states:
            for new_state in self.states_gen( state ):
                self.old_states[ new_state ] = state
                if len( set( new_state ) ) == 1:
                    print "Solution found, node = ", new_state[0]
                    self.print_path( new_state )
                    return True

                new_states.append( new_state )

        if not new_states:
            print "Solution not found"
            return True

        self.last_states = new_states
        return False

    def print_path( self, state ):
        while state:
            print repr( state )
            state = self.old_states[ state ]

# Исходные данные для 10 узлов
N = 10
roads = [ (0,1), (0,2), (1,2), (2,3), (1,3), (3,4), (4,5), (5,6), (6,7), (7,8), (8,9) ]
start = ( 0, 1, 9 )

proc = Map( N, roads, start )


while not proc.one_step():
    pass

citis=set()
roads={}
robots=[]
places=[]
where={}
time=0
nc=int(raw_input('Сколько дорог?'))
print('city1 city2 dlina')
for i in range(nc):
    s=raw_input().split()
    roads[(s[0],s[1])]=s[2]
    citis.update(set(s[:2]))
#составим список мест, где могут находиться роботы
for i in citis:
    places.append({'type':'city','obj':i})
for i in roads:
    places.append({'type':'road','obj':i})
    
nr=int(raw_input('Сколько Роботов?'))
print('city skorost')
for i in range(nr):
    s=raw_input().split()
    for (j,item) in enumerate(places):
        if item['type']=='city' and item['obj']==s[0]:
            robots.append({'place':j, 'v':s[1], 'color':i})
            break;
for i in robots: #удаляем одинаковые
    t=i
    for j in robots:
        if j['place']==t['place'] and j['v']==t['v']:
            robots.remove(j)
    robots.append(t)
nr=len(robots)
colors=[i['color'] for i in robots]
ncolors=len(colors)
def step(robots): # time+=0.5
    new_robots=[]
    for (w,i) in enumerate(robots):
        pl=places[i['place']]
        if pl['type']=='city':
            for road in roads:
                if pl['obj'] in road:
                    if i['v']==1:
                        place=places.index({'type':'road','obj':road})
                        where[w]=road[0] if pl['obj']==road[1] else road[1]
                    else:
                        place=places.index({'type':'city','obj':road[0] if pl['obj']==road[1] else road[1]})
                    new_robots.append({'place':place,'v':i['v'],'color':i['color']})
        else:#Раз робот на дороге, то его скорость равна 1
            place=places.index({'type':'city','obj':where[w]})
            new_robots.append({'place':place,'v':i['v'],'color':i['color']})
            where.pop(w)
    robots=new_robots
    #Теперь удалю одинаковых, чтобы излищне не нагружать комп.
    for i in robots:
        t=i
        while i in robots:
            robots.remove(i)
        robots.append(i)
    return robots
    
     
def is_together():
    r_in_p=[]
    for i in range(len(places)):
        r_in_p.append(0)
    for j in robots:
        r_in_p[j['place']]+=1
    if max(r_in_p)>=ncolors:
        return True
    else:
        return False
    
while not(is_together()):
    time+=0.5
    robots=step(robots)
print(time)

time+=0.5