AcWing 1129. 热浪---list,map 代替数组模拟链表建图
原题链接
简单
作者:
空空伊
,
2021-01-14 09:35:03
,
所有人可见
,
阅读 327
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N = 100010;
static int n;
static int m;
static int start;
static int end;
//<a,<b,c>>
static Map<Integer, Map<Integer, Integer>> map= new HashMap<>();
static int idx = 0;
static int[] dist = new int[N];
static boolean[] st = new boolean[N]; //标记是否在队列中
static int INF = 0x3f3f3f3f;
public static void add(int a, int b, int c) {
Map<Integer, Integer> curMap = map.getOrDefault(a,new HashMap<>());
curMap.put(b,c);
map.put(a,curMap);
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] str1 = reader.readLine().split(" ");
n = Integer.parseInt(str1[0]);
m = Integer.parseInt(str1[1]);
start = Integer.parseInt(str1[2]);
end = Integer.parseInt(str1[3]);
while(m -- > 0)
{
String[] str2 = reader.readLine().split(" ");
int a = Integer.parseInt(str2[0]);
int b = Integer.parseInt(str2[1]);
int c = Integer.parseInt(str2[2]);
add(a,b,c);
add(b,a,c);
}
int t = spfa();
System.out.println(t);
}
private static int spfa() {
Arrays.fill(dist,INF);
Queue<Integer> queue = new LinkedList<Integer>();
dist[start] = 0;
queue.add(start);
st[start] = true;//标记1号点在队列中
while (!queue.isEmpty()) {
int t = queue.poll();
st[t] = false;
Map<Integer, Integer> curMap = map.get(t);
for (Map.Entry<Integer, Integer> entry : curMap.entrySet()) {
int k = entry.getKey();
int v = entry.getValue();
if (dist[k] > dist[t] + v) {
dist[k] = dist[t] + v;
if (!st[k]) {
queue.add(k);
st[k] = true;
}
}
}
}
return dist[end];
}
}