每条边长2^K, k<=500, 若k<=64还能用Dij,相加直接用位运算即可。

而k最大可达500，还要取模，取模后不能比较大小

//将Dijkstra算法得到的n-1条路径求并集U
//1.必不存在环。因为每个结点必和前驱结点共用路径
//2.必为连通图。源点可达任意结点
//可知并集U必为生成树。不一定为最小生成树(可用三角形图举反例) 

//若图任意边权值>更小边总和，则各最短路径的并集一定是最小生成树，2^k >2^(k-1)+...+1
//证: 在最小生成树上任意增加一边E构成环，由最小生成树性质可知E为环上最大边
//    再由条件可知E边长>环上其他边总和
//    其他结点到达环上任意结点都一定不会经过E，即E不在U 
//    可知最小生成树就是U

输入的边长为有序序列，直接Kruskal O(m)得到最小生成树存入邻接表

对邻接表一次DFS O(n) 更新dist即可

#include <stdio.h>
#include <string.h>
const int MOD=100000;
struct Node{
	int e[100][2];
	int size;
	void push(int v, int w){
		e[size][0]=v; e[size][1]=w;
		size++;
	}
	void clear(){size=0;}
	int getv(int i){return e[i][0];}
	int getw(int i){return e[i][1];}
};
struct AdjM{
	Node a[100]; //邻接表
	int size;
	void clear(){
		for(register int i=0;i<size;i++)
			a[i].clear();
	}
	void push(int x,int y,int w){
		a[x].push(y,w);
		a[y].push(x,w);
	}
	Node& operator[]...