SPFA + SLF
SLF：Small Label First 策略。
实现方法是，设队首元素为
，队列中要加入节点
，在
时加到队首而不是队尾，否则和普通的 SPFA 一样加到队尾。
LLL：Large Label Last 策略。
实现方法是，设队列
中的队首元素为
，距离标号的平均值为
，每次出队时，若
，把
移到队列末尾，如此反复，直到找到一个
使
，将其出队。
/**//*
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<int, int> 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+1, false);
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
小阮 阅读(403)
评论(0) 编辑 收藏 引用 所属分类:
USACO