下面转载自: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; }
原始博客:http://www.fuxiang90.com/?p=1460