随笔-11  评论-0  文章-0  trackbacks-0
#include<iostream>
#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#include
<ctype.h>
#include
<queue>
#include
<list>
#include
<vector>
#include
<cmath>
#include
<algorithm>
using namespace std;

#define inf 1000000001

struct SNode
{
    
int to;
    
int price;
    SNode 
*next;
}
forward[1000000+10],Reverse[1000000+10],storage[2000000+10];

int P,Q,allocate;



bool visited[1000000+10];
 
int dist[1000000+10];

struct cmp{

    
bool operator()( int a, int b)
    
{
        
return dist[a]>dist[b];
    }

}
;

 priority_queue
<int,vector<int>,cmp> H;

void initial()
{
    
for(int i=0;i<=P;i++)
        Reverse[i].next 
=forward[i].next =NULL;
    allocate
=0;
}





int dijk(SNode graph[])
{
    
for(int i=0;i<=P;i++)
        dist[i]
=inf;
    memset(visited,
false,sizeof(visited));

    visited[
1]=true;
    dist[
1]=0;
    SNode 
*p=graph[1].next;    
    
while(!H.empty() )H.pop ();
    
while(p){ printf("%d     ",p->to );H.push(p->to ); dist[p->to]=p->price;p =p->next;}
    
int cnt=0;
    
while(!H.empty ()){printf("%d ",H.top ());H.pop ();}
    
while(!H.empty ()){
        
int k=0;
        
do{
            
if(H.empty ())break;
            
if(k)H.pop ();
            k
=H.top ();printf("%d -----%d--\n",k,++cnt);
            
        }
while(visited[k] );
        
if(H.empty () )break;
        H.pop ();
        printf(
"asdfsdf\n");
        visited[k]
=true;

        
// relax

        p
=graph[k].next;
        
while(p){printf("-%d- ",p->to );
            
if!visited[p->to ] &&  dist[k]+p->price< dist[p->to] ){
                
                dist[p
->to ]= dist[k]+p->price;
                H.push (p
->to );
            }

            p
=p->next;
        }

    }

    
int ret=0;
    
for(int i=1;i<=P;i++){
        ret
+=dist[i];
    }

    
return ret;
}




int main()
{
    
int T;
    scanf(
"%d",&T);
    
while(T--){
        scanf(
"%d %d",&P,&Q);
        initial();
        
int sor,des,price;
        
for(int i=0;i<Q;i++){
            scanf(
"%d %d %d",&sor,&des,&price);
            
// push
            SNode *p=&storage[allocate++];
            p
->to=des;
            p
->price=price;
            p
->next =forward[sor].next;
            forward[ sor].next 
=p;

            SNode 
*q=&storage[allocate++];
            q
->to =sor;
            q
->price=price;
            q
->next =Reverse[des].next;
            Reverse[des].next
=q;
        }

        
int ans=dijk(forward);
    ans
+=dijk(Reverse);
        printf(
"%d\n",ans);
    }

    
return 0;
}


            
posted on 2009-07-20 21:47 iyixiang 阅读(231) 评论(0)  编辑 收藏 引用 所属分类: acm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理