AcWing 3488. 散装写法
原题链接
中等
作者:
灰小白
,
2022-04-20 18:51:30
,
所有人可见
,
阅读 188
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int e[510],h[110] , ne[510] , w[510] , dis[110] , id;
bool sta[110];
int mod = 1e5 , p[110];
void add(int a, int b , int v){
e[id] = b; ne[id] = h[a] ;
w[id] = v ; h[a] = id++ ;
}
int find(int x){
return p[x] == x ? x : p[x] = find(p[x]);
}
int main()
{
int n , m , k = 1; cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ ) p[i] = i;
int a, b;
while(m--){
cin >> a >> b;
int aa = find(a) , bb = find(b);
if(aa != bb ){
p[aa] = bb;
add(a,b,k); add(b,a,k);
}
k = k * 2 % mod;
}
memset(dis, 0x3f , sizeof dis);
dis[0] = 0; int now = 0;
sta[now] = true;
for(int i = 1 ; i < n ; i++){
for(int j = h[now] ; j != -1 ; j = ne[j])
dis[e[j]] = min(dis[e[j]] , dis[now] + w[j]);
int x = 1e9 ;
for(int j = 1 ; j < n ; j++)
if(!sta[j] && dis[j] < x){
x = dis[j]; now = j;
}
sta[now] = true;
}
for (int i = 1; i < n; i ++ )
if(sta[i]) cout << dis[i] % mod <<endl;
else puts("-1");
return 0;
}