下面转载自：http://wenku.baidu.com/view/cc7585630b1c59eef8c7b45c.html
简洁起见，我们约定有向加权图G不存在负权回路，即最短路径一定存在。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。
我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
----------------
我实现的spfa 算法也是来自上面，但是速度有点慢，是在check v是否在队列中，之前没有用hash，后来用hash就快了，但是还是卡在第九个测试样例上。 最后改成临接表的形式 ， 0.1s 刷过
//int graph[N][N];
//pair 第一个是点 ，第二个是边的权值
vector< vector < pair<int ,int > > > graph; 临接表 。。。。
/*
ID:fuxiang2
PROG: butter
LANG: C++
*/#include <iostream>
#include <fstream>
#include <stack>
#include <
string>
#include <vector>
#include <queue>
#include <map>
#include <list>
#include <algorithm>
#include <
set>
#include <cmath>
#include <cstring>
#include <cstdlib>
using namespace std;
ofstream fout ("butter.out");
ifstream fin ("butter.in");
const int N = 802;
int maxN = 0x0fffffff;
//int graph[N][N];
//pair 第一个是点 ，第二个是边的权值
vector< vector < pair<
int ,
int > > > graph;
int d[N];
int cow[N];
int flag[N] ;
int n,p,c;
void spfa(
int start)
{
queue<
int > q;
q.push(start);
//初始化距离
for(
int i = 1 ; i <= p ; i ++)
d[i] = maxN;
d[start] = 0;
//memset(flag,N*sizeof(int),0); //这个在usaco编译错误
for(
int i = 1 ; i<=n ; i ++) flag[i] = 0;
flag[start] = 1;
while(!q.empty()){
int u = q.front();
q.pop();
flag[u] = 0;
for(vector<pair<
int ,
int > >::iterator iter = graph[u].begin() ; iter != graph[u].end() ; iter ++ ){
int v = iter->first;
if( d[v] > iter->second + d[u] ){
d[v] = iter->second+ d[u];
//if(queue_find(q ,v) == false){
if( flag[v] == 0){
q.push(v);
flag[v] = 1;
}
}
// }// end if
}
//end for
}
//end while
}
int main()
{
fin>>n>>p>>c;
for(
int i = 1; i <= n ; i ++){
int a;
fin>>a;
cow[a] ++;
}
// for(int i =1 ; i < N ; i ++){
// for(int j = 1 ; j < N ; j ++)
// graph[i][j] = maxN;
// }
graph.resize(N);
for(
int i = 1 ; i <= c ; i ++){
int x,y,w;
fin>> x>>y >>w;
graph[x].push_back(make_pair(y,w));
graph[y].push_back(make_pair(x,w));
}
long minN = maxN;
for(
int i = 1 ; i <= p ; i ++){
spfa(i);
long t = 0;
for(
int j = 1 ; j <= p ; j ++){
if (d[j] == maxN) {
t = maxN;
break;
}
t += cow[j]*d[j];
}
if (t < minN) minN = t;
}
fout<< minN <<endl;
return 0;
}
1 ： http://www.nocow.cn/index.php/SPFA%E7%AE%97%E6%B3%95 原始博客：http://www.fuxiang90.com/?p=1460
posted on 2012-10-26 22:28
付翔 阅读(299)
评论(0) 编辑 收藏 引用 所属分类:
ACM 数据结构