下面轉(zhuǎn)載自：http://wenku.baidu.com/view/cc7585630b1c59eef8c7b45c.html
簡(jiǎn)潔起見(jiàn)，我們約定有向加權(quán)圖G不存在負(fù)權(quán)回路，即最短路徑一定存在。當(dāng)然，我們可以在執(zhí)行該算法前做一次拓?fù)渑判?，以判斷是否存在?fù)權(quán)回路，但這不是我們討論的重點(diǎn)。
我們用數(shù)組d記錄每個(gè)結(jié)點(diǎn)的最短路徑估計(jì)值，而且用鄰接表來(lái)存儲(chǔ)圖G。我們采取的方法是動(dòng)態(tài)逼近法：設(shè)立一個(gè)先進(jìn)先出的隊(duì)列用來(lái)保存待優(yōu)化的結(jié)點(diǎn)，優(yōu)化時(shí)每次取出隊(duì)首結(jié)點(diǎn)u，并且用u點(diǎn)當(dāng)前的最短路徑估計(jì)值對(duì)離開(kāi)u點(diǎn)所指向的結(jié)點(diǎn)v進(jìn)行松弛操作，如果v點(diǎn)的最短路徑估計(jì)值有所調(diào)整，且v點(diǎn)不在當(dāng)前的隊(duì)列中，就將v點(diǎn)放入隊(duì)尾。這樣不斷從隊(duì)列中取出結(jié)點(diǎn)來(lái)進(jìn)行松弛操作，直至隊(duì)列空為止。
----------------
我實(shí)現(xiàn)的spfa 算法也是來(lái)自上面，但是速度有點(diǎn)慢，是在check v是否在隊(duì)列中，之前沒(méi)有用hash，后來(lái)用hash就快了，但是還是卡在第九個(gè)測(cè)試樣例上。 最后改成臨接表的形式 ， 0.1s 刷過(guò)
//int graph[N][N];
//pair 第一個(gè)是點(diǎn) ，第二個(gè)是邊的權(quán)值
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 第一個(gè)是點(diǎn) ，第二個(gè)是邊的權(quán)值
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); //這個(gè)在usaco編譯錯(cuò)誤
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
付翔 閱讀(360)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
ACM 數(shù)據(jù)結(jié)構(gòu)