forked from sherxon/AlgoDS
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathElectrificationPlan1982.java
More file actions
147 lines (113 loc) · 3.99 KB
/
ElectrificationPlan1982.java
File metadata and controls
147 lines (113 loc) · 3.99 KB
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
package timus;
import java.util.*;
/**
* Created by sherxon on 2016-11-24.
*/
public class ElectrificationPlan1982 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] f=in.nextLine().split(" ");
int n = Integer.parseInt(f[0]);
int k = Integer.parseInt(f[1]);
Set<Integer> cities = new HashSet<>(k);
String[] s=in.nextLine().split(" ");
for (int i = 0; i < s.length; i++) {
cities.add(Integer.parseInt(s[i]));
}
EGraph graph= new EGraph();
for (int i = 1; i <=n; i++) {
graph.addVertex(i, cities.contains(i));
}
String[] a;
for (int i = 0; i < n; i++) {
a=in.nextLine().split(" ");
for (int j = i+1; j <a.length ; j++) {
graph.addEdge(i+1, j+1, Integer.parseInt(a[j]));
}
}
System.out.println(graph.mst());
}
private static class EGraph {
public int mst(){
List<Integer> unvisited= new ArrayList<>(map.keySet());
Integer vertex=unvisited.get(0);
unvisited.remove(vertex);
PriorityQueue<VE> queue=new PriorityQueue<>();
while (!unvisited.isEmpty()){
VE v=map.get(vertex);
for (EEdge outEdge : v.outEdges) {
if( outEdge.to.des > outEdge.weight+ v.des){
outEdge.to.des=outEdge.weight+ v.des;
queue.add(outEdge.to);
}else if(outEdge.to.isPS && outEdge.from.des > outEdge.weight){
outEdge.from.des=outEdge.weight;
queue.add(outEdge.to);
queue.add(outEdge.from);
}
}
if(queue.size()==0)break;
VE minVertex = queue.remove();
unvisited.remove(minVertex.label);
vertex=minVertex.label;
}
int cost=0;
for (Integer integer : map.keySet()) {
cost+=map.get(integer).des;
}
return cost;
}
private Map<Integer, VE> map = new HashMap<>();
public void addVertex(Integer v, boolean contains){
VE ve=new VE(v);
ve.isPS=contains;
if(contains)ve.des=0;
else ve.des=Integer.MAX_VALUE;
map.putIfAbsent(v,ve);
}
public void addEdge(Integer f, Integer t, int weight){
VE from=map.get(f);
VE to=map.get(t);
if(from.isPS && to.isPS)return;
EEdge edge= new EEdge(from, to, weight);
map.get(f).outEdges.add(edge);
EEdge edge2= new EEdge(to, from, weight);
map.get(t).outEdges.add(edge2);
map.get(f).inEdges.add(edge2);
map.get(t).inEdges.add(edge);
}
private class VE implements Comparable {
private Integer label;
private List<EEdge> inEdges;
private List<EEdge> outEdges;
private boolean isPS;
public boolean visited;
public int des;
public VE(Integer label) {
this.label = label;
this.inEdges=new ArrayList<>();
this.outEdges=new ArrayList<>();
}
@Override
public int compareTo(Object o) {
return this.des - ((VE)o).des;
}
}
static class EEdge implements Comparable{
VE from;
VE to;
int weight;
public EEdge(int weight) {
this.weight = weight;
}
public EEdge(VE from, VE to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public int compareTo(Object o) {
return this.weight - ((EEdge)o).weight;
}
}
}
}