poj 1125 最短路

好的，请稍等，我为您提供poj 1125 最短路的解法和代码。

题目描述

在一个n个点的有向图中，每个点有一个编号(1<=编号<=n)，每条边有一个长度。现在给定一个起点s，要求计算出从s出发到每个点的最短路。若两点间没有路，则认为它们之间的长度为无限大。

输入格式：

第一行是一个整数n，表示点数；接下来的n行中，第i行表示点i的出边(若干个)，每个出边包含两个整数，第一个是该出边指向的点的编号，第二个是该出边的长度；最后一行是起点s的编号。

输出格式：

输出共n行，每行一个整数，表示从s到该点的最短路。

样例输入

5
2 2 3 1 5 5
3 2 1 1
1 1
4 3 5 1
5

样例输出

3
2
0
6
5

解法

本题可以用Dijkstra算法求解最短路，Dijkstra算法是一种贪心算法，每次选择当前到起点距离最短的节点进行扩展，直到所有节点都被扩展。因为每次扩展的节点都是当前距离最短的，所以可以保证得到的是最短路径。

具体实现时，可以用一个数组dist[i]来记录起点s到节点i的最短距离，初始时dist[s]=0，其余节点的dist[i]=∞。每次选择一个未被扩展过的距离起点最近的节点v，将v扩展并更新其邻接点的距离dist。

代码实现

下面是Java语言的代码实现，时间复杂度为O(n^2)。

相关问题

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++;
    }
}