一个农场有很多块牧场(<=800),这些牧场间有很多条(<=1450)道路相连,一些牛分散在这些牧场中。在这些牧场中寻找一个牧场,使得所有的牛到达该牧场所走的路程和最小,当然牛牛们会自己寻找到达该牧场的最短路径。
题目意图很明确,显然需要寻找每两个牧场间的最短路径,自然想到Floyd算法。不过该算法时间复杂度为O(V^3),对此题来说就是 800*800*800=512000000,超时是必然的。之后就可以考虑 Heap 优化的 Dijkstra 算法和 SPFA 算法了。此题中是稀疏图,考虑先用一下 SPFA 看看情况。
#include<fstream>
#include<vector>
#include<list>
#include<queue>
using namespace std;
const int infinite=1000000000;
int nCow,nPasture,nConnect;
vector<int> vCowsAt;
vector< list< pair<int,int> > > vPasAjt;
inline bool relax(int u, int v, int weight, vector<int> &d){
int newlength=d[u]+weight;
if(newlength<d[v]){
d[v]=newlength;
return true;
}
return false;
}
int CalPathSum(int iSource){
queue<int> Q;
vector<bool> IsInQ(nPasture);
vector<int> d(nPasture,infinite);
d[iSource]=0;
Q.push(iSource);
IsInQ[iSource]=true;
while(!Q.empty()){
int u=Q.front();
Q.pop();
IsInQ[u]=false;
for(list< pair<int,int> >::iterator itr=vPasAjt[u].begin();itr!=vPasAjt[u].end();++itr){
int v=itr->first;
if(relax(u,v,itr->second,d) && !IsInQ[v]){
Q.push(v);
IsInQ[v]=true;
}
}
}
int sum=0;
for(int i=0;i<nCow;++i)sum+=d[vCowsAt[i]];
return sum;
}
int main(){
ifstream fin("butter.in");
ofstream fout("butter.out");
fin>>nCow>>nPasture>>nConnect;
vCowsAt.resize(nCow);
vPasAjt.resize(nPasture);
for(int i=0;i<nCow;++i){
int iPasture;
fin>>iPasture;
vCowsAt[i]=iPasture-1;
}
for(int i=0;i<nConnect;++i){
int u,v,distance;
fin>>u>>v>>distance;
vPasAjt[u-1].push_back(pair<int,int>(v-1,distance));
vPasAjt[v-1].push_back(pair<int,int>(u-1,distance));
}
int minpath=infinite;
for(int i=0;i<nPasture;++i)
minpath=min(minpath,CalPathSum(i));
fout<<minpath<<endl;
}
果然不错,一次就通过了:
TASK: butter
LANG: C++
Compiling…
Compile: OK
Executing…
Test 1: TEST OK [0.011 secs, 2848 KB]
Test 2: TEST OK [0.011 secs, 2848 KB]
Test 3: TEST OK [0.000 secs, 2848 KB]
Test 4: TEST OK [0.011 secs, 2848 KB]
Test 5: TEST OK [0.011 secs, 2852 KB]
Test 6: TEST OK [0.011 secs, 2852 KB]
Test 7: TEST OK [0.065 secs, 2852 KB]
Test 8: TEST OK [0.108 secs, 2852 KB]
Test 9: TEST OK [0.184 secs, 2848 KB]
Test 10: TEST OK [0.194 secs, 2848 KB]
All tests OK.
YOUR PROGRAM (‘butter’) WORKED FIRST TIME! That’s fantastic
— and a rare thing. Please accept these special automated
congratulations.
之后看了下标程,用的是 Dijkstra + Heap ,写起来果然很复杂,花了150多行……就用标程也运行了一下做个比较:
Executing…
Test 1: TEST OK [0.000 secs, 9416 KB]
Test 2: TEST OK [0.011 secs, 9416 KB]
Test 3: TEST OK [0.000 secs, 9420 KB]
Test 4: TEST OK [0.000 secs, 9420 KB]
Test 5: TEST OK [0.000 secs, 9420 KB]
Test 6: TEST OK [0.011 secs, 9420 KB]
Test 7: TEST OK [0.043 secs, 9420 KB]
Test 8: TEST OK [0.108 secs, 9416 KB]
Test 9: TEST OK [0.216 secs, 9420 KB]
Test 10: TEST OK [0.205 secs, 9420 KB]
All tests OK.
从最后两个测试时间来看,两个算法相差不大。不过 SPFA 要稍稍快一些。嗯,现在至少在稀疏图上验证了 SPFA 的效率,下次遇到稠密图再试一下吧。