gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
POJ 1511(SPFA)
  1#include <cstdio>
  2#include <cstring>
  3
  4const int MAXN = 10100000 ;
  5const __int64 INT_MAX = 2000000000 ;
  6
  7struct NODE
  8{
  9    int v ;
 10    __int64 w ;
 11    NODE *next ;
 12}edge[MAXN], redge[MAXN], g_Temp[MAXN * 2] ;
 13
 14int g_Pos = 0 ;
 15
 16__int64 ecost[MAXN] ;
 17int N , M , W , Q[MAXN];
 18
 19bool visited[MAXN] ;
 20
 21bool SPFA(bool rg = false)
 22{
 23    int  h = 0 , t = 1 , u ;
 24    NODE *ptr ;
 25
 26    memset(visited, 0, sizeof(visited)) ;
 27
 28    for ( int i = 0 ; i <= N ; ++i )
 29        ecost[i] = INT_MAX ;
 30    Q[0] = 1 ;
 31
 32    ecost[1] = 0 ;
 33
 34    while ( h != t )
 35    {
 36        u = Q[h] ;
 37        h++ ;
 38
 39        visited[u] = false ;
 40
 41        if ( !rg )
 42            ptr = edge[u].next ;
 43        else
 44            ptr = redge[u].next ;
 45        
 46        while ( ptr ){
 47            if ( ecost[ptr->v] > ecost[u] + ptr->w )    //松弛操作
 48            {
 49                ecost[ptr->v] = ecost[u] + ptr->w ;    
 50                if ( !visited[ptr->v] )
 51                {
 52                    Q[t] = ptr->v ;
 53                    t++ ;                    
 54                    visited[ptr->v] = true ;                    
 55                }
 56            }
 57            ptr = ptr->next ;
 58        }
 59    }
 60
 61    return ( ecost[N] != INT_MAX ) ;
 62}
 63
 64void Insert( const int& x, const int& y, const __int64& w )
 65{
 66    NODE *ptr = &g_Temp[g_Pos++] ;
 67    ptr->v = y ;
 68    ptr->w = w ;
 69    ptr->next = edge[x].next ;
 70    edge[x].next = ptr ;
 71
 72    ptr = &g_Temp[g_Pos++] ;
 73    ptr->v = x ;
 74    ptr->w = w ;
 75    ptr->next = redge[y].next ;
 76    redge[y].next = ptr ;
 77}
 78
 79void Init()
 80{
 81    g_Pos = 0 ;
 82
 83    for ( int i = 0 ; i <= N ; ++i )
 84    {
 85        edge[i].next = NULL ;
 86        redge[i].next = NULL ;
 87    }
 88}
 89
 90int main()
 91{
 92    int t , i , x , y ;
 93    __int64 w ;
 94    __int64 ans ;
 95
 96    scanf("%d", &t) ;
 97
 98    while ( t-- )
 99    {
100        scanf("%d %d", &N, &M) ;
101
102        Init() ;
103        for ( i = 0 ; i < M ; ++i )
104        {
105            scanf("%d %d %I64d", &x, &y, &w) ;
106            Insert( x, y, w ) ;
107        }
108
109        ans = 0 ;
110
111        //照样对正反图求最短路
112        SPFA() ;
113
114        for ( i = 2 ; i <= N ; ++i )
115        {
116            ans += ecost[i] ;
117        }
118
119        SPFA( true ) ;
120
121        for ( i = 2 ; i <= N ; ++i )
122            ans += ecost[i] ;
123
124        printf("%I64d\n", ans) ;
125    }
126
127    return 0 ;
128}
posted on 2008-11-19 23:46 巫 阅读(266) 评论(0)  编辑 收藏 引用 所属分类: 图论

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