1. 场景、模型
多个起点,多个终点,在任选起点的情况下,求到各个终点的最短距离。
2. 与floyd场景的区别
floyd是精细的求出任意两点的最短距离。
而本题问的是在可选起点的情况下,到各个终点的最短距离。
3. 暴力
很容易想到暴力,用spfa循环n次求出每个起点到终点的最短距离取min。
时间复杂度o(nm),但有多组测试数据所以非常危险。
4. 创建虚拟原点
创建一个虚拟原点,原点与每个起点连一条权重为0的边。
这种做法有点像哨兵,像n*n的地图状压一直算到第n+1个,目的是将多种情况归结于同一种情况,从而简便计算。
5. 代码
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N = 1010, M = 21010, INF = 0x3f3f3f3f;
static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
static int[] dist = new int[N];
static int n, m, idx = 0, E;
static boolean[] st = new boolean[N];
static int[] q = new int[N];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s;
while ((s = br.readLine()) != null ) {
//h和idx都要初始化
Arrays.fill(h, -1);
idx = 0;
String[] s1 = s.split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
E = Integer.parseInt(s1[2]);
while (m -- > 0) {
String[] s2 = br.readLine().split(" ");
int a = Integer.parseInt(s2[0]);
int b = Integer.parseInt(s2[1]);
int c = Integer.parseInt(s2[2]);
add(a, b, c);
}
String[] s3 = br.readLine().split(" ");
int T = Integer.parseInt(s3[0]);
String[] s4 = br.readLine().split(" ");
for (int i = 0; i < T; i++) {
int S = Integer.parseInt(s4[i]);
add(0, S, 0);//建立虚拟源点0
}
spfa();
if (dist[E] == INF)
System.out.println(-1);
else
System.out.println(dist[E]);
}
}
public static void spfa() {
Arrays.fill(st, false);
Arrays.fill(dist, INF);
int hh = 0, tt = 1;
q[0] = 0;
dist[0] = 0;
while (hh != tt) {
int t = q[hh ++];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if (!st[j]) {
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
}
public static void add (int a, int b, int c) {
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx ++ ;
}
}