-
Notifications
You must be signed in to change notification settings - Fork 0
/
Alex Travelling.java
56 lines (48 loc) · 1.39 KB
/
Alex Travelling.java
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
class Solution {
class Pair{
int node, weight;
Pair(int n, int w){
node=n;
weight=w;
}
}
int minimumCost(int[][] flights, int n, int k) {
// Your code here
Map<Integer, ArrayList<Pair>> map=new HashMap<>();
for(int []i:flights){
int u=i[0];
int v=i[1];
int w=i[2];
map.putIfAbsent(u, new ArrayList<>());
map.get(u).add(new Pair(v,w));
}
int dis[]=new int[n+1];
int ans=0;
Queue<Pair> q=new LinkedList<>();
q.add(new Pair(k, dis[k]));
while(!q.isEmpty()){
Pair curr=q.remove();
int node=curr.node;
int cost=curr.weight;
if(!map.containsKey(node))
continue;
for(Pair p:map.get(node)){
int neb=p.node;
int nebCost=p.weight;
if((dis[neb]==0 || dis[neb]>cost+nebCost) && neb!=k){
dis[neb]=cost+nebCost;
q.add(new Pair(neb, dis[neb]));
}
}
}
for(int i=1;i<dis.length;i++){
if(dis[i]!=0){
ans=Math.max(ans,dis[i]);
}
else if(i!=k){
return -1;
}
}
return ans;
}
}