gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
POJ 3268(最短路径 SPFA)

跟POJ 1511一样

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

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