好题!并查集生成Kruskal+队列优化Dijkstra
Prim和Dijkstra除点权更新方式不同以外,其余遍历方式均相同,所以练了本题等于同时练了Prim和Kruskal~
Prim生成后的两点之间的路径是唯一的(若不唯一,则可以绕起点和终点成圈,说明我们生成的图不是最小生成树)。
因此,我们不必在意边权具体是多少,只要让最短路径经过的点数最小即可。
又:路径经过的点数最小等同于经过边数最小, 在代码实现中,由于边权均小于MOD,且MOD*MAXN<INT_MAX一定成立,
因此我们可以用在初始化中已经对MOD取过模的边权之和最小代替经过边数最小,作为Dijkstra状态更新的依据~
代码如下:
#include<cstdio> #include<vector> #include<queue> #include<algorithm> #define MOD 100000 #define MAXN 100 #define MAX 1e9 struct node{ int weight; int nodeIdx; node(int w, int i):weight(w), nodeIdx(i){} }; struct cmp{ bool operator()(node a, node b){ return a.weight>b.weight; } }; std::priority_queue<node, std::vector<node>, cmp> queue; std::vector<node> edges[MAXN]; int father[MAXN]; int dis[MAXN]; int find(int x){ while(father[x]!=x){ x=father[x]; } return x; } bool merge(int x, int y){ int fx = find(x); int fy = find(y); if(fx!=fy){ father[fx]=fy; } return fx!=fy; } int main(){ int n, m; scanf("%d%d",&n,&m); for(int i=0;i<n;++i){ father[i]=i; dis[i]=MAX; } dis[0]=0; for(int i=0, len=1;i<m;++i,len=(2*len)%MOD){ int u, v; scanf("%d%d",&u,&v); if(merge(u,v)){ edges[v].push_back(node(len, u)); edges[u].push_back(node(len, v)); } } std::fill(dis, dis+n, MAX); dis[0] = 0; queue.push(node(0, 0)); while(!queue.empty()){ auto nd = queue.top(); queue.pop(); int from = nd.nodeIdx; if(nd.weight>dis[from]) continue; for(auto edge: edges[from]){ int to = edge.nodeIdx; int w = edge.weight; if(dis[to]>dis[from]+w){ dis[to] = dis[from]+w; queue.push(node(dis[to], to)); } } } for(int i=1;i<n;++i){ if(dis[i]==MAX){ printf("-1\n"); }else{ printf("%d\n", dis[i]%MOD); } } return 0; }