kuangbin专题四 最短路练习

tips:大家评论的时候写一下邮箱和昵称呀,头像是根据昵称和邮箱随机生成的😁

kuangbin专题合集

ACM正确入门方式——数学lover

题目列表

  1. POJ 2387 Til the Cows Come Home AC: 2020-02-05 21:08:20
  2. POJ 2253 Frogger AC: 2020-02-11 20:17:15
  3. POJ 1797 Heavy Transportation AC: 2020-02-16 23:14:29
  4. POJ 3268 Silver Cow Party AC: 2020-02-18 23:39:25
  5. POJ 1860 Currency Exchange
  6. POJ 3259 Wormholes
  7. POJ 1502 MPI Maelstrom
  8. POJ 3660 Cow Contest
  9. POJ 2240 Arbitrage
  10. POJ 1511 Invitation Cards
  11. POJ 3159 Candies
  12. POJ 2502 Subway
  13. POJ 1062 昂贵的聘礼
  14. POJ 1847 Tram AC: 2018-07-22 01:13:19
  15. LightOJ 1074 Extended Traffic
  16. HDU 4725 The Shortest Path in Nya Graph
  17. HDU 3416 Marriage Match IV
  18. HDU 4370 0 or 1
  19. POJ 3169 Layout

POJ-2387 Til the Cows Come Home

题意

有N个点,T条边,每条边都是双向边。让你求出从点N走到点1的最短路。。。

题解

(wrtm,sb题坑死我了,写的我怀疑智商,一个dijkstra模板题WA了六发。。。)
dijkstra模板题,没什么好说的,注意是双向边,如果用邻接矩阵的话要注意可能有重边,邻接表就不用管有没有重边了。
最主要的是他题目中说的每条边的范围是1-100,然后我最大值就用1000了,结果一直WA,我佛了。。。最后改成了1<<30才过的。。。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import java.util.*;

class Edge implements Comparable<Edge> {
public int t, d;

public Edge(int t, int d) {
this.t = t;
this.d = d;
}

public int compareTo(Edge o) {
if (this.d > o.d) {
return 1;
} else if (this.d == o.d) {
return 0;
} else {
return -1;
}
}
}

public class Main {

public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int t = cin.nextInt();
int n = cin.nextInt();

int dis[] = new int[n + 10];
List[] lists = new List[n + 10];

for (int i = 0; i < lists.length; i++) {
lists[i] = new ArrayList<Edge>();
}

for (int i = 0; i < t; i++) {
int u = cin.nextInt(), v = cin.nextInt(), d = cin.nextInt();
lists[u - 1].add(new Edge(v - 1, d));
lists[v - 1].add(new Edge(u - 1, d));
}

for (int i = 0; i < n; i++) {
dis[i] = (i == n - 1) ? 0 : (1 << 30);
}

PriorityQueue<Edge> pQueue = new PriorityQueue<Edge>();
Edge now = new Edge(n - 1, dis[n - 1]);
pQueue.add(now);

while (!pQueue.isEmpty()) {
now = pQueue.poll();
int x = now.t;

for (int i = 0; i < lists[x].size(); i++) {
Edge next = (Edge) lists[x].get(i);
int y = next.t, w = next.d;
if (dis[x] + w < dis[y]) {
dis[y] = dis[x] + w;
pQueue.add(new Edge(y, dis[y]));
}
}
}

System.out.println(dis[0]);
}

}

POJ-2253 Frogger

题意

有两只青蛙分别在两个石头上,他们中间有一些石头,青蛙Freddy想要跳到青蛙Fiona那里,求出两个青蛙之间的青蛙距离。(那么什么是青蛙距离呢,一开始看题的时候我也一脸懵逼,这个minimax distance是个神tm的玩意儿???)

青蛙距离:两个点之间有若干条路径可以互通,青蛙距离就是取每条路径中的最长边中的最小值
假如从点a到点b有两条路径分别为:a->c->b,a->e->b;其中ac长度为6cb长度为9ae长度为3eb长度为10。那么第一条路径中最长的一条边就是cb,第二条路径中最长的一条边就是eb,青蛙路径就是取cb和eb中较小的一个,即a到b的青蛙距离为9。

题解

其实就是把最短路的定义改了一下,原来最短路的定义是两点之间的最短距离,现在是两点之间路径中最长边的最小值,就把dijkstra、SPFA或Floyd中的松弛操作的公式改一下就行了,其他照旧。因为这个题是完全图,所以用邻接矩阵比较容易一些。
别给我说两点之间的距离公式不会。。。

img

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Point {
public Point(double x, double y) {
super();
this.x = x;
this.y = y;
}

double x, y;

}

public class Main {
static double dis[] = new double[300];
static int n;
static double[][] mp = new double[300][300];

public static void dijkstra() {
boolean vis[] = new boolean[n+10];
for (int i = 0; i < vis.length; i++) {
vis[i] = false;
}

for (int i = 0; i < n; i++) {
double mn = 100000.0;
int x=0;
for (int j = 0; j < n; j++) {
if (!vis[j] && dis[j]<mn) {
mn = dis[j];
x = j;
}
}

if (mn == 100000.0) {
return;
}
vis[x] = true;
for (int j = 0; j < n; j++) {
dis[j] = Math.min(dis[j], Math.max(mp[x][j],mn));
}
}
}

public static void main(String[] args) {

Scanner cin = new Scanner(System.in);
int t=0;

while (true) {
n = cin.nextInt();
t++;
if (n == 0) {
break;
}
List<Point> points = new ArrayList<Point>();
dis[0] = 0;
mp[0][0] = 0;
double x, y;
for (int i = 0; i < n; i++) {
x = cin.nextInt();
y = cin.nextInt();

if (i != 0) {
for (int j = 0; j < points.size(); j++) {
double z = Math.sqrt((points.get(j).x - x) * (points.get(j).x - x)
+ (points.get(j).y - y) * (points.get(j).y - y));//两点之间的距离公式
if (j == 0) {
dis[i] = z;
}
mp[i][j] = z;
mp[j][i] = z;
}
}
points.add(new Point(x, y));
}

dijkstra();
System.out.println("Scenario #" + t + "\nFrog Distance = " + String.format("%.3f", dis[1]) + "\n");
}
}

}

POJ-1797 Heavy Transportation

题意

这题和青蛙跳(上一题POJ2253)那一题正好相反,求每种路径中权重最小的一节之中的最大值

题解

可以用堆优化,但是好麻烦,懒得想了,直接邻接矩阵+普通djikstra。。。把松弛操作改成Max(dis, Min(x, y)),注意组数据输出时要输出两个换行。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.util.Scanner;

public class Main {

public static void dijkstra(int n) {
for (int i = 0; i < n; i++) {
dis[i] = mp[0][i];
vis[i] = false;
}

for (int i = 0; i < n; i++) {
int mx = -INF;
int x = 0;
for (int j = 0; j < n; j++) {
if (mx < dis[j] && !vis[j]) {
x = j;
mx = dis[j];
}
}

if (mx == -INF) {
return;
}
vis[x] = true;

for (int j = 0; j < n; j++) {
dis[j] = Math.max(dis[j], Math.min(mx, mp[x][j]));
}
}
}

public static int dis[] = new int[1010];
public static int mp[][] = new int[1010][1010];
public static int INF = 1<<30;
public static boolean vis[] = new boolean[1010];

public static void main(String[] args) {

Scanner cin = new Scanner(System.in);
int t = cin.nextInt();

for (int i = 0; i < t; i++) {
int n = cin.nextInt();
int m = cin.nextInt();

for (int j = 0; j < 1010; j++) {
for (int j2 = 0; j2 < 1010; j2++) {
mp[j][j2] = -INF;
}
}
int x, y, z;
for (int j = 0; j < m; j++) {
x = cin.nextInt()-1;
y = cin.nextInt()-1;
z = cin.nextInt();

mp[x][y] = z;
mp[y][x] = z;
}

dijkstra(n);
System.out.println("Scenario #" + (i+1) + ":\n" + dis[n-1] + "\n");
}
}

}

POJ-3268 Silver Cow Party

题意

有n个农场,每个农场有一头牛,n个农场之间有m条单向路,其他农场的牛都要去x农场开会,开完会再回自己的农场,每头牛保证都会走最短路径,求出走路最多的牛来回共走了多少路。

题解

由于是单向路,所以来回可能走的路径不同。但是,我们直接建两个图不就好了,反向建一张图,正向建一张图,那这道题就成了分别求两个图x点的单源最短路,直接跑两遍dijkstra就行了。

我看评论区还有人用Floyd,肯定超时啊,N最大是1000,M最大是100000。。。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

class Edge implements Comparable<Edge> {
int t, d;

public Edge(int t, int d) {
super();
this.t = t;
this.d = d;
}

@Override
public int compareTo(Edge o) {
if (this.d > o.d) {
return 1;
} else if (this.d == o.d) {
return 0;
} else {
return -1;
}
}

}

public class Main {

public static int INF = 1 << 30;
public static int dis1[] = new int[1010];
public static int dis2[] = new int[1010];
public static List<Edge> list1[] = new List[1010];
public static List<Edge> list2[] = new List[1010];

public static void main(String[] args) {

Scanner cin = new Scanner(System.in);

int n = cin.nextInt(), m = cin.nextInt(), x = cin.nextInt();

for (int i = 0; i < 1010; i++) {
list1[i] = new ArrayList<Edge>();
list2[i] = new ArrayList<Edge>();
dis1[i] = (i == x - 1) ? 0 : INF;
dis2[i] = (i == x - 1) ? 0 : INF;
}
int s = 0, t = 0, d = 0;
for (int i = 0; i < m; i++) {
s = cin.nextInt() - 1;
t = cin.nextInt() - 1;
d = cin.nextInt();

list1[s].add(new Edge(t, d));
list2[t].add(new Edge(s, d));
}

PriorityQueue<Edge> pQueue1 = new PriorityQueue<Edge>();
PriorityQueue<Edge> pQueue2 = new PriorityQueue<Edge>();
Edge now = new Edge(x - 1, 0);
pQueue1.offer(now);
pQueue2.offer(now);

while (!pQueue1.isEmpty()) {
now = pQueue1.poll();
s = now.t;

for (int i = 0; i < list1[s].size(); i++) {
Edge next = (Edge) list1[s].get(i);
t = next.t;
d = next.d;

if (dis1[t] > dis1[s] + d) {
dis1[t] = dis1[s] + d;
pQueue1.offer(new Edge(t, dis1[t]));
}
}
}

while (!pQueue2.isEmpty()) {
now = pQueue2.poll();
s = now.t;

for (int i = 0; i < list2[s].size(); i++) {
Edge next = (Edge) list2[s].get(i);
t = next.t;
d = next.d;

if (dis2[t] > dis2[s] + d) {
dis2[t] = dis2[s] + d;
pQueue2.offer(new Edge(t, dis2[t]));
}
}
}


int mx = -INF;
for (int i = 0; i < n; i++) {
dis1[i] += dis2[i];
mx = Math.max(dis1[i], mx);
}

System.out.println(mx);
}

}
Donate comment here