poj 1125 最短路

题目描述

给定一张n个点的有向图，无自环，没有重边，每条边有一个时间和一个花费。求起点到终点的最短时间和最小花费。

输入格式

第一行一个正整数n，表示点数。

接下来nn行，每行n个整数，表示邻接矩阵，其中-1表示无边，其他数字表示边的时间。

再接下来一行，nn个整数，表示每条边的花费，其中-1表示这条边不存在。

输出格式

输出两个整数，分别表示最短时间和最小花费。

如果不存在从起点到终点的路径，输出-1 -1。

数据范围

1≤n≤100

输入样例1：

4
0 2 -1 5
-1 0 2 -1
-1 -1 0 3
-1 -1 -1 0
1 2 3 4

输出样例1：

7 6

输入样例2：

4
0 2 -1 5
-1 0 2 -1
-1 -1 0 3
-1 -1 -1 0
-1 -1 -1 -1

输出样例2：

-1 -1

算法1

(Dijkstra) $O(n^2)$

这道题是最短路模板题，可以使用Dijkstra算法求解。

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(Bellman-Ford) $O(n^3)$

这道题也可以使用Bellman-Ford算法求解。

时间复杂度

参考文献

C++ 代码

相关问题

POJ 2253 ——Frogger——————【最短路、Dijkstra、最长边最小化】

好的，这是一道经典的最短路问题，题目大意是有一只青蛙要从起点跳到终点，有一些石头可以跳，每个石头有一个固定的位置和耗费，青蛙可以在石头之间跳跃，但是跳跃的距离不能超过石头的耗费，求青蛙从起点到终点的最短距离。

这道题可以使用Dijkstra算法来解决，我们可以将石头看作图中的点，石头之间的跳跃看作图中的边，每个石头的位置和耗费可以看作点的权值。

具体来说，我们可以先将起点加入到一个优先队列中，起点的距离为0。然后我们每次从优先队列中取出距离起点最近的点进行松弛操作，即对于每个相邻的石头，如果从当前点到该石头的距离小于该石头的当前最短距离，则更新该石头的最短距离并将其加入到优先队列中。最后，当我们取出终点时，其最短距离即为答案。

需要注意的是，这道题中跳跃的距离不能超过石头的耗费，因此我们可以将跳跃的距离看作边的权值，求最短路时，可以将边权取相反数，这样Dijkstra算法求出的最短路即为跳跃的耗费之和。

代码实现如下：

poj1985java

根据提供的引用[1]，这是一道求解最远距离的问题，可以使用图论中的最短路算法来解决。而引用则提供了一种解决树上最远距离的方法，可以通过找到树的直径来解决。下面是一种Java实现的树的直径算法：

import java.util.*;

public class Main {
    static int N = 100010, idx;
    static int h[] = new int[N], e[] = new int[N << 1], ne[] = new int[N << 1], w[] = new int[N << 1];
    static int dist[] = new int[N];
    static boolean st[] = new boolean[N];
    static int n, res;

    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        Arrays.fill(h, -1);
        for (int i = 0; i < n - 1; i++) {
            int a = scan.nextInt(), b = scan.nextInt(), c = scan.nextInt();
            add(a, b, c);
            add(b, a, c);
        }
        dfs(1);
        Arrays.fill(st, false);
        dfs(idx);
        System.out.println(res);
    }

    static void dfs(int u) {
        st[u] = true;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!st[j]) {
                dfs(j);
                if (dist[u] + w[i] > res) {
                    res = dist[u] + w[i];
                    idx = j;
                }
                dist[u] = Math.max(dist[u], dist[j] + w[i]);
            }
        }
    }

    static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}