-
Notifications
You must be signed in to change notification settings - Fork 0
/
28 Junee.cpp
54 lines (49 loc) · 1.31 KB
/
28 Junee.cpp
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
// wrong solution
class Solution {
public:
map<int,int>mp;
bool comp (map<int,int>a , map<int,int>b){
return a[0][second] > b[0][second];
}
bool present(vector<vector<int>>& roads , int x){
for(int i = 0; i < roads.size(); i++){
if(x == roads[i][0] || x == roads[i][1]){
mp[x]++;
}
}
return true;
}
long long maximumImportance(int n, vector<vector<int>>& roads) {
for(int i = 0; i < n ; i++){
if(present(roads,i)){
mp[i]++;
}
}
sort(mp.begin(),mp.end(),comp);
int sum = 0;
for(int i = 0; i < roads.size(); i++){
if(mp.find(roads[i][0]) != mp.end()){
sum += mp[roads[i][0]];
}
if(mp.find(roads[i][1]) != mp.end()){
sum += mp[roads[i][1]];
}
}
return sum;
}
};
// right solution
class Solution {
public:
long long maximumImportance(int n, vector<vector<int>>& roads) {
long res = 0, cost = 1;
vector<int> conn(n, 0);
for (auto road : roads) {
conn[road[0]]++;
conn[road[1]]++;
}
sort(conn.begin(), conn.end());
for (auto con : conn) res += con * (cost++);
return res;
}
};