题目看着向生成树,但实际上是最短路径+堆优化。
#include <stdio.h>

const int LEN = 50005;
const __int64 MAX = 0x7fffffffffffffff;

struct HEAD
  {
int next;
int last;
__int64 dis;
int used;
}head[LEN];

struct NODE
  {
int num;
__int64 len;
int next;
}node[LEN*2];
int next;

//堆部分
int hash[LEN]; //堆中部分现在所在的位置
struct HEAP
  {
int num; //指向堆外面
__int64 dis;
}heap[LEN];
int hlen; //堆大小

__int64 weight[LEN]; //记录重量

inline void init ( int v )
  {

hlen = 0;
next = 0;
for ( int i=0; i<v; i++ )
 {
head[i].dis = MAX;
head[i].next = -1;
head[i].used = 0;
}
}

void ins ( int a, int b, __int64 len )
  {

node[next].num = b;
node[next].next = -1;
node[next].len = len;
next ++;

if ( head[a].next==-1 )
head[a].next = next-1;
else
node[ head[a].last ].next = next-1;
head[a].last = next-1;
}

inline void swap ( int a, int b )
  {

struct
 {
__int64 dis;
int num;
}temp;

temp.dis = heap[a].dis;
temp.num = heap[a].num;
heap[a].dis = heap[b].dis;
heap[a].num = heap[b].num;
heap[b].dis = temp.dis;
heap[b].num = temp.num;
}

inline void moveup ( int p )
  {

while ( p>0&&heap[(p-1)/2].dis>heap[p].dis )
 {
hash[ heap[p].num ] = (p-1)/2;
hash[ heap[ (p-1)/2 ].num ] = p;
swap ( p, (p-1)/2 );
p = (p-1)/2;
}
}

inline void movedown ( int p )
  {

int flag = 1;
while ( p<hlen&&flag )
 {
int lson = p*2+1;
int rson = p*2+2;
flag = 0;
if ( rson<hlen )
 {
if ( heap[lson].dis<=heap[rson].dis&&heap[lson].dis<heap[p].dis )
 {
hash[ heap[p].num] = lson;
hash[ heap[lson].num] = p;
swap ( p, lson );
p = lson;
flag = 1;
}
else if ( heap[rson].dis<=heap[lson].dis&&heap[rson].dis<heap[p].dis )
 {
hash[ heap[p].num] = rson;
hash[ heap[rson].num] = p;
swap ( p, rson );
p = rson;
flag = 1;
}
}
else if ( lson<hlen )
 {
if ( heap[lson].dis<heap[p].dis )
 {
hash[ heap[p].num] = lson;
hash[ heap[lson].num] = p;
swap ( p, lson );
p = lson;
flag = 1;
}
}
}
}

void dj ( int s, int n )
  {

head[s].dis = 0;
for ( int i=0; i<n; i++ )
 {
heap[hlen].dis = head[i].dis;
heap[hlen].num = i;
hlen ++;
hash[i] = hlen-1;
moveup ( hlen-1 );
}
for ( int i=0; i<n-1; i++ )
 {
__int64 min0;
int min1;
min0 = heap[0].dis;
min1 = heap[0].num;
if ( min0==MAX )
return;
head[min1].used = 1;
int tmp = heap[hlen-1].num;
hash[tmp] = 0;
hash[min1] = hlen-1;
swap ( 0, hlen-1 );
hlen--;
moveup ( hash[tmp] );
movedown ( hash[tmp] );
for ( int j=head[min1].next; j!=-1; j=node[j].next )
 {
int e = node[j].num;
__int64 t_dis = head[min1].dis+node[j].len;
if ( t_dis<head[e].dis )
 {
head[e].dis = t_dis;
heap[hash[e]].dis = t_dis;
moveup ( hash[e] );
}
}
}
}

int main ()
  {

int t;
scanf ( "%d", &t );
while ( t-- )
 {
int v, e;
scanf ( "%d%d", &v, &e );
for ( int i=0; i<v; i++ )
scanf ( "%I64d", &weight[i] );
init ( v );
for ( int i=0; i<e; i++ )
 {
int a, b;
__int64 len;
scanf ( "%d%d%I64d", &a, &b, &len );
if ( a!=b )
 {
ins ( a-1, b-1, len );
ins ( b-1, a-1, len );
}
}

dj ( 0, v );
__int64 ans = 0;
for ( int i=0; i<v; i++ )
 {
if ( head[i].dis==MAX )
 {
ans = -1;
break;
}
ans += head[i].dis*weight[i];
}
if ( ans==-1 )
printf ( "No Answer\n" );
else
printf ( "%I64d\n", ans );
}
return 0;
}


|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
24 | 25 | 26 | 27 | 28 | 29 | 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 | 1 | 2 | 3 | 4 | 5 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论

阅读排行榜
评论排行榜
|
|