【问题描述】最短路径问题实际上是带权有向图（网）的一种应用，用Dijkstra算法求两个顶点间的最短路径。备注：输入的有向网信息中0表示不存在顶点到自身的弧，32767表示两个顶点之间不存在弧。 【输入形式】带权有向图（网）的顶点数及，有向图（网）的信息，出发顶点。 【输出形式】输出出发顶点到有向图（网）其余顶点间的最短路径长度及其路径。 【样例输入】 输入顶点数： 7 输入有向网的信息： 0 4 6 6 32767 32767 32767 32767 0 1 32767

这是一个典型的最短路径问题，可以使用 Dijkstra 算法来解决。以下是 Python 代码实现：

import sys

MAX = 32767

def dijkstra(graph, start):
    n = len(graph)
    visited = [False] * n
    dist = [MAX] * n
    path = [-1] * n
    dist[start] = 0

    for i in range(n):
        min_dist = MAX
        u = -1
        for j in range(n):
            if not visited[j] and dist[j] < min_dist:
                min_dist = dist[j]
                u = j
        if u == -1:
            break
        visited[u] = True
        for v in range(n):
            if not visited[v] and graph[u][v] != MAX:
                new_dist = dist[u] + graph[u][v]
                if new_dist < dist[v]:
                    dist[v] = new_dist
                    path[v] = u

    return dist, path

def find_shortest_path(path, start, end):
    shortest_path = [end]
    while end != start:
        end = path[end]
        shortest_path.append(end)
    shortest_path.reverse()
    return shortest_path

n = int(input("输入顶点数："))
graph = []
for i in range(n):
    row = list(map(int, input("输入第{}行有向网的信息：".format(i+1)).split()))
    graph.append(row)

start = int(input("输入出发顶点："))
dist, path = dijkstra(graph, start)

for i in range(n):
    if i != start:
        print("从{}到{}的最短路径长度为{}，路径为{}".format(start, i, dist[i], find_shortest_path(path, start, i)))

输入样例：

输入顶点数：7
输入第1行有向网的信息：0 4 6 6 32767 32767 32767
输入第2行有向网的信息：32767 0 1 32767 32767 5 32767
输入第3行有向网的信息：32767 32767 0 32767 32767 32767 6
输入第4行有向网的信息：32767 32767 2 0 3 32767 32767
输入第5行有向网的信息：32767 32767 32767 32767 0 32767 4
输入第6行有向网的信息：32767 32767 32767 32767 32767 0 6
输入第7行有向网的信息：32767 32767 32767 32767 32767 32767 0
输入出发顶点：0

输出结果：

从0到1的最短路径长度为4，路径为[0, 1]
从0到2的最短路径长度为5，路径为[0, 1, 2]
从0到3的最短路径长度为5，路径为[0, 3]
从0到4的最短路径长度为8，路径为[0, 3, 4]
从0到5的最短路径长度为11，路径为[0, 1, 5]
从0到6的最短路径长度为14，路径为[0, 1, 2, 6]