随笔-141  评论-9  文章-3  trackbacks-0
SPFA  + SLF

SLF:Small Label First 策略。
实现方法是,设队首元素为 $i$,队列中要加入节点 $j$,在 $d_j \le d_i$ 时加到队首而不是队尾,否则和普通的 SPFA 一样加到队尾。

LLL:Large Label Last 策略。
实现方法是,设队列 $Q$ 中的队首元素为 $i$,距离标号的平均值为 ,每次出队时,若 $d_i > \overline d$,把 $i$ 移到队列末尾,如此反复,直到找到一个 $i$ 使 $d_i \le \overline d$,将其出队。

/*
ID: lorelei3
TASK: butter
LANG: C++
*/


#include 
<fstream>
#include 
<queue>
#include 
<vector>
#include 
<functional>

using namespace std;

const int MAXN = 850;
const int INF = 9999999;

typedef pair
<intint>        PAIR;
vector
< vector< PAIR > >     map;
vector
<int>        cow;

int N,P,C;

inline 
bool relax(int u, int v, int weight, vector<int> &dist){
    
int len = dist[u] + weight;
    
if(len<dist[v]){
        dist[v] 
= len;
        
return true;
    }

    
return false;
}


int SPFA(int k){
    
    deque
<int>        Q;
    vector
<int>        dist(P+1, INF);
    vector
<bool>    InQ(P+1false);

    dist[k] 
= 0;
    InQ[k] 
= true;
    Q.push_back(k);
    
while(!Q.empty()){
        
int u = Q.front();
        Q.pop_front();
        InQ[u] 
= false;
        
for(vector<PAIR>::iterator iter = map[u].begin(); iter!=map[u].end(); ++iter){
            
int v = (*iter).first;
            
int w = (*iter).second;
            
if(relax(u, v, w, dist) && !InQ[v]){
                
if(dist[v]<dist[u])    Q.push_front(v);
                
else    Q.push_back(v);
                InQ[v] 
= true;
            }

        }

    }


    
int sum=0;
    
for(int i=0 ; i<N; ++i)
        sum 
+= dist[cow[i]];
    
return sum;
}


inline 
int min(int a, int b){
    
return a<b? a: b;
}


int main(){
    
int i,j,a,b,v,c,ans=INF;
    ifstream fin(
"butter.in");
    ofstream fout(
"butter.out");

    fin
>>N>>P>>C;

    map.resize(MAXN);
    cow.resize(MAXN);

    
for(i=0; i<N; ++i)
        fin
>>cow[i];

    
for(i=0; i<C; ++i){
        fin
>>a>>b>>v;
        map[a].push_back(make_pair(b,v));
        map[b].push_back(make_pair(a,v));
    }


    
for(i=1; i<P+1++i)
        ans 
= min(ans, SPFA(i));
    
    fout
<<ans<<endl;

    
return 0;
}

posted on 2011-01-02 13:20 小阮 阅读(416) 评论(0)  编辑 收藏 引用 所属分类: USACO

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