图中的最短路径
没有权值的图中的最短路径
直接用BFS来遍历，就可以求出最短路径。使用队列来求解
有权值的图中的最短路径
直接用BFS来遍历，就可以求出最短路径。使用优先队列来求解
package writeTest
.zhongxing
;
import java
.util
.*
;
public class Main1 {
private static int[][] road
;
private static ArrayList
<Integer> list
;
public static void main(String
[] args
) {
Scanner sc
= new Scanner(System
.in
);
int n
= sc
.nextInt();
int m
= sc
.nextInt();
int q
= sc
.nextInt();
road
= new int[m
][3];
PriorityQueue
<Integer
[]> queue
= new PriorityQueue<>((o1
, o2
) -> (o1
[1]-o2
[1]));
for (int i
= 0; i
< m
; i
++) {
int x
= sc
.nextInt();
int y
= sc
.nextInt();
int num
= sc
.nextInt();
road
[i
][0]=x
;
road
[i
][1]=y
;
road
[i
][2]=num
;
}
list
= new ArrayList<>();
for (int i
= 0; i
< q
; i
++) {
int x
= sc
.nextInt();
int y
= sc
.nextInt();
if (x
==y
){
System
.out
.println(0);continue;
}
System
.out
.println(s(x
, y
));
}
}
private static int s(int x
, int y
) {
PriorityQueue
<Integer
[]> queue
= new PriorityQueue<>((o1
, o2
) -> (o1
[1]-o2
[1]));
for (int i
= 0; i
< road
.length
; i
++) {
if (road
[i
][0]==x
)queue
.add(new Integer[]{road
[i
][1],road
[i
][2]});
if (road
[i
][1]==x
)queue
.add(new Integer[]{road
[i
][0],road
[i
][2]});
}
HashSet
<Integer> set
= new HashSet<>();
set
.add(x
);
while (!queue
.isEmpty()){
Integer
[] poll
= queue
.poll();
if (poll
[0]==y
)return poll
[1];
int length
=poll
[1];
set
.add(poll
[0]);
for (int i
= 0; i
< road
.length
; i
++) {
if (road
[i
][0]==poll
[0]){
if (!set
.contains(road
[i
][1]))
queue
.add(new Integer[]{road
[i
][1],road
[i
][2]+length
});
}
if (road
[i
][1]==poll
[0]){
if (!set
.contains(road
[i
][0]))
queue
.add(new Integer[]{road
[i
][0],road
[i
][2]+length
});
}
}
}
return -1;
}
}
