付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0


下面转载自: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 付翔 阅读(269) 评论(0)  编辑 收藏 引用 所属分类: ACM 数据结构

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2012年10月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜