2

In [ ]:

from queue import PriorityQueue
import numpy as np

from queue import PriorityQueue import numpy as np

In [ ]:

d = None

d = None

In [ ]:

class State:
    def __init__(self,room, g):
        self.room = room
        self.g = g
        self.h = self.H()
        self.f = self.g + self.h
    def __lt__(self, other):
        return self.f < other.f
    
    def H(self):  
        if self.room == N:  # 已经到底部了
            return 0
        minn = 66666666 
        #找到最小的出边
        for i in islink[self.room]:
            if dis[self.room,i] < minn:
                minn = dis[self.room,i]

        if(minn == 66666666):
            return 0
        else:
            return minn
    '''
    def H(self):
        # 另一种思路
        return d[self.room]
    '''

class State: def __init__(self,room, g): self.room = room self.g = g self.h = self.H() self.f = self.g + self.h def __lt__(self, other): return self.f < other.f def H(self): if self.room == N: # 已经到底部了 return 0 minn = 66666666 #找到最小的出边 for i in islink[self.room]: if dis[self.room,i] < minn: minn = dis[self.room,i] if(minn == 66666666): return 0 else: return minn ''' def H(self): # 另一种思路 return d[self.room] '''

In [ ]:

def FindNextRoom(NowRoom):
    NextRoom = []
    for i in islink[NowRoom]:
        NextRoom.append(i)
    
    return NextRoom

def FindNextRoom(NowRoom): NextRoom = [] for i in islink[NowRoom]: NextRoom.append(i) return NextRoom

In [ ]:

def Astar(start):
    pq = PriorityQueue()
    cost = [] # 每条路径的代价
    state = State(start, 0)
    pq.put(state)

    # 找K条路
    while not pq.empty() and len(cost) < K:
        state = pq.get()
        if state.room == N:  # 到底了
            cost.append(state.g)
        NextRoom = FindNextRoom(state.room)
        for i in NextRoom:
            stateNext = State(i, state.g + dis[state.room, i])
            pq.put(stateNext)

    if len(cost) < K:
        for i in range(K - len(cost)):
            cost.append(-1)

    for i in cost:
        print(i)

def Astar(start): pq = PriorityQueue() cost = [] # 每条路径的代价 state = State(start, 0) pq.put(state) # 找K条路 while not pq.empty() and len(cost) < K: state = pq.get() if state.room == N: # 到底了 cost.append(state.g) NextRoom = FindNextRoom(state.room) for i in NextRoom: stateNext = State(i, state.g + dis[state.room, i]) pq.put(stateNext) if len(cost) < K: for i in range(K - len(cost)): cost.append(-1) for i in cost: print(i)

In [ ]:

def dijkstra(N,dis):
    vis = [False] * (N+1)
    d = [66666666] * (N+1)
    d[N] = 0
    pq = PriorityQueue()
    pq.put((0,N))
    while not pq.empty():
        dist,node = pq.get()
        if vis[node]:
            continue
        vis[node]=True
        for nei in range(1,N+1):
            if dis[node][nei]>0:
                new_dist = dist+dis[node][nei]
                if new_dist < d[nei]:
                    d[nei] = new_dist
                    pq.put((new_dist,nei))
    return d

def dijkstra(N,dis): vis = [False] * (N+1) d = [66666666] * (N+1) d[N] = 0 pq = PriorityQueue() pq.put((0,N)) while not pq.empty(): dist,node = pq.get() if vis[node]: continue vis[node]=True for nei in range(1,N+1): if dis[node][nei]>0: new_dist = dist+dis[node][nei] if new_dist < d[nei]: d[nei] = new_dist pq.put((new_dist,nei)) return d

In [ ]:

In [ ]:

if __name__ == "__main__":
    tmp = input().split()
    N, M, K = list(map(int,tmp))
    rooms = []
    dis = np.zeros((N+1,N+1), dtype=int)
    dis2 = np.zeros((N+1,N+1), dtype=int)
    islink =  [ [] for i in range(N+1) ]

    for i in range(M):
        tmp = input().split()
        rooms.append(list(map(int, tmp)))
        dis[rooms[i][0], rooms[i][1]] = rooms[i][2]
        islink[rooms[i][0]].append(rooms[i][1])
        dis2[rooms[i][1], rooms[i][0]] = rooms[i][2]
    
    d = dijkstra(N,dis2)
    Astar(1)

if __name__ == "__main__": tmp = input().split() N, M, K = list(map(int,tmp)) rooms = [] dis = np.zeros((N+1,N+1), dtype=int) dis2 = np.zeros((N+1,N+1), dtype=int) islink = [ [] for i in range(N+1) ] for i in range(M): tmp = input().split() rooms.append(list(map(int, tmp))) dis[rooms[i][0], rooms[i][1]] = rooms[i][2] islink[rooms[i][0]].append(rooms[i][1]) dis2[rooms[i][1], rooms[i][0]] = rooms[i][2] d = dijkstra(N,dis2) Astar(1)