#include <stdio.h>
#include <string.h>
#define N 1000001
#define M 1000001
#define inf 0x7fffffff
/*堆中节点*/
typedef struct nnode
{
int key; //对应图中的节点
int dis; //距离
}nnode;
nnode hnode[N];
int conv[N]; //图中的节点对应到二叉树的位置
/*邻接表节点*/
typedef struct node
{
int key;
int dis;
struct node *next;
}node;
node *vert[N], edge[M], *_vert[N], _edge[M];
int visited[N];
int heap_size = 0;
void swp(struct nnode *a, struct nnode *b)
{
struct nnode tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void swp_int(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//调整堆
void heapify(int i)
{
int l = i << 1;
int r = (i << 1) + 1;
int min;
if(l <= heap_size && hnode[l].dis < hnode[i].dis)
min = l;
else
min = i;
if(r <= heap_size && hnode[min].dis > hnode[r].dis)
min = r;
if(min != i)
{
swp(&hnode[i], &hnode[min]);
conv[hnode[i].key] = i; //这个也要相应改变
conv[hnode[min].key] = min;
heapify(min);
}
}
//初始化二叉查找树的节点
void init(int s, int n)
{
int i;
for(i=1; i<=n; i++)
{
hnode[i].key = i;
hnode[i].dis = inf;
conv[i] = i;
}
hnode[s].dis = 0;
}
//建树
void build(int n)
{
int i;
heap_size = n;
for(i=n/2; i>=1; i--)
{
heapify(i);
}
}
//取得根节点, 并自顶向下调整
int get_min()
{
int min = hnode[1].key;
swp(&hnode[1], &hnode[heap_size]);
conv[hnode[1].key] = 1;
conv[hnode[heap_size].key] = heap_size;
heap_size--;
heapify(1);
return min;
}
// 松弛操作
void relax(int u, node *p, node *vert[])
{
int tmp;
int vv = conv[p->key];
if(hnode[vv].dis > hnode[conv[u]].dis + p->dis)
{
hnode[vv].dis = hnode[conv[u]].dis + p->dis;
while(vv > 1) //节点最短距离改变了,所以树也要调整,从下往上交换
{
tmp = vv >> 1;
if(hnode[tmp].dis > hnode[vv].dis)
{
swp(&hnode[tmp], &hnode[vv]);
swp_int(&conv[hnode[tmp].key], &conv[hnode[vv].key]);
}
vv = tmp;
}
}
}
//核心,dijkstra算法 ,跟一般的一样,除了取得最小距离的点是从查找二叉树取的
//本来是O(n),改进到O(log n),于是总的复杂度为O(nlogn)
long long dij(int s, int n, node *vert[])
{
int u, i;
long long ans = 0;
node *p;
init(s, n);
build(n);
while(heap_size > 0)
{
u = get_min();
visited[u] = 1;
for(p=vert[u]; p; p=p->next)
{
if(p->dis < inf)
relax(u, p, vert);
}
}
for(i=1; i<=n; i++)
ans += hnode[i].dis;
return ans;
}
int main()
{
int t, n, m;
int a, b, c;
int i;
freopen("i.in", "r", stdin);
scanf("%d", &t);
while(t--)
{
for(i=1; i<N; i++)
{
vert[i] = NULL;
_vert[i] = NULL;
}
scanf("%d%d", &n, &m);
for (i=0; i<m; i++)
{
scanf("%d%d%d", &a, &b, &c);
edge[i].key = b;
edge[i].dis = c;
edge[i].next = vert[a];
vert[a] = &edge[i];
_edge[i].key = a;
_edge[i].dis = c;
_edge[i].next = _vert[b];
_vert[b] = &_edge[i];
}
printf("%lld\n", dij(1, n, vert)+ dij(1, n, _vert));
}
return 0;
}
|