下面轉載自：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
付翔 閱讀(328)
評論(0) 編輯 收藏 引用 所屬分類:
ACM 數據結構