Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

For this question, how to deal with the problem in the same direction, and how to discretize if the interval of the same group is too large

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef long long ll;
map<pair<int,int>,vector<pair<ll,ll>>> mp;  // 注意里面是用vector装着 
signed main(){
	int n;
	cin >> n;
	int ans = 0;
	int num = 0;
	for(int i=1;i<=n;i++){
		int a,b,c;
		cin >> a >> b >> c;
		int d= abs(__gcd(a,b));  // 请注意这个 gcd 是两个下划线
		// 且要取绝对值 
		mp[{a/d,b/d}].push_back({a*a+b*b,c});
		ans += c;
	}
	for(auto u:mp){
		vector<pair<ll,ll>> t = u.second;
		sort(t.begin(),t.end());
		int len = t.size();
		for(int i=0;i<len;i++){
			if(t[i].second!=1) num++;
			else if((i+1)==len || t[i+1].second!=1) num++;
		}
	}
	cout << ans << " " << num;
	return 0;
}
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

#include<bits/stdc++.h>
using namespace std;

const int N = (int)1e3 + 5;
int e[N * N], ne[N * N], h[N], idx = 0;
int energy[N * N], va[N * N];
int vis[N];
int di[N];

void add(int a, int b, int ener, int value) {
    e[++idx] = b;
    ne[idx] = h[a]; h[a] = idx;
    energy[idx] = ener, va[idx] = value;
}
int n, m;
int maxdistance = 0xfffffff;
int start;  // 设置为全局变量

int dikj() {
    priority_queue<pair<int, int>> q;
    int ma = 0;
    //vis[start] = 1; // 记录一下
    for (int i = 0; i <= n; i++) vis[i] = 0,di[i] = 0xffffff;
    //vis[start] = 1;
    q.push({ 0,start });
    while (q.size()) {
        int dis = -q.top().first, node = q.top().second;
        q.pop();
        if (vis[node]) continue;
        vis[node] = 1;
        for (int i = h[node]; i != -1; i = ne[i]) {
            int to = e[i];
            //if (vis[to]) continue;
            //vis[to] = 1;
            int newdis = energy[i] + dis; // 这是新的距离
            if (newdis < di[to]) {
                di[to] = newdis;
                q.push({ -newdis, to });
            }
           /* ma = max(ma, newdis);*/
            
        }
    }
    for (int i = 1; i <= n; i++) {
        if (di[i] == 0xffffff) continue;
        ma = max(ma, di[i]);
    }
    return ma;
}
int pre[N];// 记录前缀
int ju[N];
void solve(int start) {
    for (int i = 1; i <= n; i++) {
        pre[i] = i, vis[i] = 0, di[i] = 0xffffff;
    }
    priority_queue<pair<int, int>> q;
    q.push({ 0,start });
    //vis[start] = 1;
    while (q.size()) {
        int dis = -q.top().first, node = q.top().second;
        q.pop();
        //
        if (vis[node]) continue;
        vis[node] = 1;
        for (int i = h[node]; i != -1; i = ne[i]) {
            int to = e[i];
            //if (vis[to]) continue;
            //vis[to] = 1;
            int t = dis + energy[i];
            if (t < di[to]) {
                di[to] = t; pre[to] = node;
                ju[to] = ju[node] + va[i];
                q.push({ -t,to });
                //cout << "1 to: " << to << " node " << node << endl;
            }
            else if (t == di[to]) {
                int u = ju[node] + va[i];
                if (u > ju[to]) {
                    di[to] = t; pre[to] = node;
                    ju[to] = ju[node] + va[i];
                    //q.push({ -t,to });
                    //cout << "2 to: " << to << " node " << node << endl;
                }
            }
        }
    }
}


void print(int s, int t) {
    if (s == t) {
        printf("%d", s);
        return;
    }
    print(s, pre[t]);
    printf("->%d", t);

}
int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        add(a, b, c, d);
        add(b, a, c, d);
    }
    int kaishi;
    for (int i = 1; i <= n; i++) {
        start = i;
        int d = dikj();
        //cout << d << endl;
        if (d < maxdistance) {
            kaishi = start;
            maxdistance = d;
        }
    }

    cout << kaishi << endl;
    solve(kaishi);
    //int o = kaishi;
    int t;
    cin >> t;
    //for (int i = 1; i <= n; i++) {
    //    cout << pre[i] << endl;
    //}
    di[kaishi] = ju[kaishi] =0 ;
    for (int i = 1; i <= t; i++) {
        int a;
        cin >> a;
        print(kaishi,a);
        cout << endl;
        cout << di[a] << " " << ju[a] << endl;
    }
}
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