poj 1125 最短路
时间: 2024-02-10 15:56:41 浏览: 32
题目描述:
在一个城市里有N个交叉口和M条道路,每条道路连接两个交叉口,有可能两个交叉口之间有多条道路。每条道路都有一个长度,表示两个交叉口之间的距离。现在我们定义一个交叉口的权值为从起点到这个交叉口所需的最短距离,求出每个交叉口的权值。
输入格式:
第一行包含一个整数N,表示交叉口的数量。
接下来M行,每行包含三个整数a,b,c,表示交叉口a和交叉口b之间有一条长度为c的道路。
输出格式:
输出N行,每行包含一个整数,第i行表示从起点到第i个交叉口的最短距离。
数据范围:
1≤N≤100
1≤M≤10000
1≤c≤1000
样例:
输入:
3
1 2 2
1 3 4
2 3 1
输出:
0
2
3
算法1
(最短路径算法--Dijkstra) $O(N^2)$
最短路径算法--Dijkstra
时间复杂度
参考文献
python3 代码
C++ 代码
算法2
(暴力枚举) $O(n^3)$
blablabla
时间复杂度
参考文献
C++ 代码
相关问题
POJ 2253 ——Frogger——————【最短路、Dijkstra、最长边最小化】
好的,这是一道经典的最短路问题,题目大意是有一只青蛙要从起点跳到终点,有一些石头可以跳,每个石头有一个固定的位置和耗费,青蛙可以在石头之间跳跃,但是跳跃的距离不能超过石头的耗费,求青蛙从起点到终点的最短距离。
这道题可以使用Dijkstra算法来解决,我们可以将石头看作图中的点,石头之间的跳跃看作图中的边,每个石头的位置和耗费可以看作点的权值。
具体来说,我们可以先将起点加入到一个优先队列中,起点的距离为0。然后我们每次从优先队列中取出距离起点最近的点进行松弛操作,即对于每个相邻的石头,如果从当前点到该石头的距离小于该石头的当前最短距离,则更新该石头的最短距离并将其加入到优先队列中。最后,当我们取出终点时,其最短距离即为答案。
需要注意的是,这道题中跳跃的距离不能超过石头的耗费,因此我们可以将跳跃的距离看作边的权值,求最短路时,可以将边权取相反数,这样Dijkstra算法求出的最短路即为跳跃的耗费之和。
代码实现如下:
poj1985java
根据提供的引用[1],这是一道求解最远距离的问题,可以使用图论中的最短路算法来解决。而引用则提供了一种解决树上最远距离的方法,可以通过找到树的直径来解决。下面是一种Java实现的树的直径算法:
```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++;
}
}
```
相关推荐
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)