https://www.acwing.com/activity/content/competition/problem_list/3648/

B题收获：

1.利用题目告诉的结论：1e9范围质数之差小于300
2.一个数不被2-a的任何数整除 等价于他的最小质因子需要大于a

c题：初步宏观思路：不难想到用并查集维护类别，只需将每一个类缩成一个点，由于最多只有500个类别，跑一个floyd就可以了

部分细节处理：我的思路是类别用并查集维护，开了一个哈希表去存每个类别对应的根节点是最终floyd的第几个点，in fact，这样做复杂了。一会说正解，然后我在读入边的时候去判断，如果两个不是同一类，我们需要建图存边。
如果是同一类，我们只要0边，因为题目要求内部距离为0。在check的时候，本质上是看看联通性，因为我们又弄了一个并查集去看联通性，但是只合并了内部0的边，最后看看每个类别的size是不是和原先dsu=相同。
就这样交了一发,然后wa了,发现内部的两个点可以通过外部实现联通（分组：1和2，3。。。1与3联通，2与3联通,那么1和2联通，上面的做法被hack。
所以我们必须考虑合并所有为0的边，最后check的时候是对所有点看看相邻的点，如果是同一类却在维护联通性并查集中不同root，直接retur no。

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
//# define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define double long double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"

const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int a[N];
int d[502][502];
int k;//k类
unordered_map<int,int>mp;//按类别缩点以后的根对应的编号
int cnt=0;//记录当前是第几个类
void floyd(){
	
	for(int v=1;v<=k;v++){
		for(int i=1;i<=k;i++){
			for(int j=1;j<=k;j++){
				d[i][j]=min(d[i][v]+d[v][j],d[i][j]);
			}
		}
	}
}
struct DSU {
  vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};
void solve(){
	cin>>n;
	DSU dsu(n+1);DSU fn(n+1);
	cin>>m;
	cin>>k;
	int val=1;
	for(int i=1;i<=k;i++){
		mp[val]=++cnt;
		int c;
		cin>>c;
		for(int j=val;j<=val+c-1;j++){
			dsu.merge(val,j);
		}
		val=val+c;
	}
	 for (int i = 1; i <= k; i ++ )
        for (int j = 1; j <= k; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = inf;
	while(m--){
		int u,v,w;
		cin>>u>>v>>w;
		int r1=dsu.find(u),r2=dsu.find(v);
		if(r1==r2){
			if(w)continue;
			else {
				fn.merge(u,v);
			}
		}
		else {
			if(w==0)fn.merge(u,v);
			int ve1=mp[r1],ve2=mp[r2];
			d[ve2][ve1]=d[ve1][ve2]=min(d[ve1][ve2],w);
			
		}
	}
	//bool flag=true;
	for(int i=2;i<=n;i++){
		int s1=dsu.find(i-1),s2=dsu.find(i);//类别
		int r1=fn.find(i-1),r2=fn.find(i);//仅通过0边看是不是联通
	if(s1==s2&&r1!=r2){
		cout<<"No"<<endl;;
		return ;	}
	}
	cout<<"Yes"<<endl;
	floyd();
for(int i=1;i<=k;i++){
	for(int j=1;j<=k;j++){
		if(d[i][j]==inf)cout<<-1<<" ";
		else cout<<d[i][j]<<" ";
	}
	cout<<endl;
}
}
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t;
 t=1;

    while (t--) {
solve();
    }
    return 0;
}

#正解：我们只需要用一个id数组存下每个点对应的类别，在维护连通性的时候使用并查集，最后check的时候我们只需要保证两个同类别的点属于同一个根至于这个根是不是原来这个类在这个问题中我们并不关心，因为我们只关心连通性。

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
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e5 + 10, M = 510, INF = 0x3f3f3f3f;

int n, m, k;
int id[N];
int p[N];
int dist[M][M];

int find(int x) {
  if (p[x] != x) p[x] = find(p[x]);
  return p[x];
}

bool verify() {
  for (int i = 2; i <= n; i++)
    if (id[i - 1] == id[i] && find(i - 1) != find(i))
      return false;

  return true;
}

void floyd() {
  for (int u = 0; u < k; u++)
    for (int i = 0; i < k; i++)
      for (int j = 0; j < k; j++)
        dist[i][j] = min(dist[i][j], dist[i][u] + dist[u][j]);
}

int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 0, j = 1; i < k; i++) {
    int cnt;
    scanf("%d", &cnt);
    while (cnt--) id[j++] = i;
  }

  memset(dist, 0x3f, sizeof dist);
  for (int i = 0; i < k; i++) dist[i][i] = 0;
  for (int i = 1; i <= n; i++) p[i] = i;

  for (int i = 0; i < m; i++) {
    int a, b, w;
    scanf("%d%d%d", &a, &b, &w);

    if (!w && find(a) != find(b))
      p[find(a)] = find(b);

    int u = id[a], v = id[b];
    dist[u][v] = dist[v][u] = min(dist[u][v], w);
  }

  if (verify()) {
    puts("Yes");

    floyd();

    for (int i = 0; i < k; i++) {
      for (int j = 0; j < k; j++) {
        if (dist[i][j] == INF)
          dist[i][j] = -1;
        printf("%d ", dist[i][j]);
      }
      puts("");
    }
  } else {
    puts("No");
  }

  return 0;
}