1028 迪杰斯特拉算法

朴灿烈づ我的快乐病毒、 2022-09-12 00:57 368阅读 0赞

Description

  1. 给定n(n<=500)个顶点,以及E(E<=10000)条边，使用迪杰斯特拉算法计算顶点s到顶点t的最短路径.

Input

  1. 第一行输入T表示有T组数据。每组数据第一行输入n、E、s、t，分别表示顶点数、边数、顶点s以及顶点t. 接下来
  2. 输入E行每行三个正整数u(1<=u<=n)、v(1<=v<=n)、w，表示顶点u到顶点v之间无向边长度w（可能有重边）。

Output

  1. 输出T行正整数，第i行表示第i组数据s到达t的最短路径长度。若s无法到达t国，输出-1.

Sample Input

  1. 3
  2. 2 2 1 2
  3. 1 2 1
  4. 1 2 2
  5. 3 1 1 3
  6. 2 3 1
  7. 3 3 1 3
  8. 1 2 1
  9. 1 2 3
  10. 2 3 1

Sample Output

  1. 1
  2. -1
  3. 2

发表评论

表情：
评论列表 （有 0 条评论，368人围观）

还没有评论，来说两句吧...

相关阅读

    相关 迪杰斯特拉算法

    迪杰斯特拉算法 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决

    ╰半夏微凉°╰半夏微凉°/ 0 赞/ 84 阅读

    相关 迪杰斯特拉算法

    一：迪杰斯特拉算法 迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。它的主要特点是以 起始点为中心向外层层扩展(广度优先搜索思

    古城微笑少年丶古城微笑少年丶/ 0 赞/ 376 阅读

    相关 迪杰斯特拉算法（Dijkstra）证明

    首先，这篇文章是在讲《图论》时候写文章 （所以，还是以理论为主，以后有空的时候，会把代码发上来，不过我觉得大家看完理论，如果讲得好，代码也就比较容易了。如果讲得不好，网上

    男娘i男娘i/ 0 赞/ 392 阅读

    相关 Python实现迪杰斯特拉算法

    一、 迪杰斯特拉算法思想 Dijkstra算法主要针对的是有向图的单元最短路径问题，且不能出现权值为负的情况！Dijkstra算法类似于贪心算法，其应用根本在于最短路径的最

    女爷i女爷i/ 0 赞/ 404 阅读