对于APSP问题如果用单源最短路径算法的话，曾考虑过用先求出的最短路径优化，使得在后面求新源点的最短路径时对已求过的点之间可以一次优化到最终结果避免多次进入队列更新，这个优化对SPFA算法尤其明显。不过这样一来就需要用邻接矩阵储存边，对稀疏图来说需要空间比较多，也可以看成是一种DP的思想吧(空间换时间)。虽然最短路存在了邻接矩阵中，但对稀疏图计算时还是用邻接表算，这个效率依然是最高的(实践验证过，用时相差10倍以上)。

 

今天实践了一下，发现具体实现和开始想的优化方法还有些不同：只能在求过的点中取一点进行优化(多了效果不升反降)

---

#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;
vector< vector<int> > vDistMatrix;

 

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);

 

// optimizing begin:
    if(iSource>0){
        int iShort=0;
        for(int k=1;k<iSource;++k)if(vDistMatrix[k][iSource]<vDistMatrix[iShort][iSource])
            iShort=k;
        for(int iDes=0;iDes<nPasture;++iDes)
            vDistMatrix[iSource][iDes]=vDistMatrix[iShort][iSource]+vDistMatrix[iShort][iDes];
    }
// optimizing end.

 

    vDistMatrix[iSource][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,vDistMatrix[iSource]) && !IsInQ[v]){
                Q.push(v);
                IsInQ[v]=true;
            }
        }
    }

 

    int sum=0;
    for(int i=0;i<nCow;++i)sum+=vDistMatrix[iSource][vCowsAt[i]];
    return sum;
}

 

int main(){
    ifstream fin("butter.in");
    ofstream fout("butter.out");

    fin>>nCow>>nPasture>>nConnect;
    vCowsAt.resize(nCow);
    vPasAjt.resize(nPasture);
    vDistMatrix.resize(nPasture);

    for(int i=0;i<nPasture;++i)
        vDistMatrix[i].resize(nPasture,infinite);

    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;
}

---

程序变化不大，只是多了对 vDistMatrix 矩阵的处理，并加上了优化部分(已标出)。由于使用了动态空间分配，内存占用没有想象的增加那么多。

下面是运行结果：

---

TASK: butter