青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

枯葉北風(fēng)寒,忽然年以殘,念往昔,語(yǔ)默心酸。二十光陰無(wú)一物,韶光賤,寐難安; 不畏形影單,道途阻且慢,哪曲折,如渡飛湍。斬浪劈波酬壯志,同把酒,共言歡! -如夢(mèng)令

POJ 1511-Invitation Cards(SPFA算法)

今天終于用SPFA寫(xiě)出了第一個(gè)程序,感覺(jué)收獲很大,從Dij到Floyed再到Bellmen,以及今天的SPFA,每一種算法背后都蘊(yùn)藏著許多值得思考的地方。正因?yàn)檠芯苛怂鼈儯攀沟梦业哪芰Σ粩嗟孬@得了提高。
之前以為SPFA做為最短路問(wèn)題最快的算法,想必代碼定不好寫(xiě),不過(guò)今天研究過(guò)才知道,SPFA的代碼量遠(yuǎn)遠(yuǎn)不及Dij,這著實(shí)令人驚嘆,原來(lái)最好的算法SPFA是如此的好寫(xiě),呵呵 我想此算法在很大程度上可以完全代替之前的算法,以后再碰到最短路問(wèn)題時(shí),SPFA一定能成為首要的選擇!
PS:由于是用鄰接表來(lái)存儲(chǔ)的,所以每次操作前要收回以前分配的內(nèi)存,我嘗試了收回和不收回兩種方法,發(fā)現(xiàn)其實(shí)差別不大,如果純粹是比賽的話,可能不收回反而會(huì)更好些(避免超時(shí))。當(dāng)然如果在實(shí)際應(yīng)用中,應(yīng)該切記內(nèi)存的分配,否則軟件可能會(huì)發(fā)生異常。

//Coded by abilitytao 
//Time:2009-04-10 22:49:58
#include<iostream>
#include
<cmath>
#include
<queue>
using namespace std;
#define MAX_NUM 1000000001
#define MAX_DOTNUM 1000001

int n,m;
queue
<int>myqueue;
bool mark[MAX_DOTNUM];
__int64 dis[MAX_DOTNUM];


struct node
{

    
int v;
    
int w;
    node 
*next;
}
edge[MAX_DOTNUM];//此鄰接表用于存儲(chǔ)正向圖

node reversed_edge[MAX_DOTNUM];
//此逆鄰接表用于存儲(chǔ)逆向圖

void initial(node edge[])//鄰接表的初始化,里面封裝了回收上一次操作所分配之內(nèi)存的操作
{
    
int i;
    node 
*p;
    node 
*q;
    
for(i=1;i<=n;i++)
    
{
        p
=&edge[i];
        q
=p->next;
        
while(q!=NULL)
        
{
            p
->next=q->next;
            delete q;
            q
=p->next;
        }

    }

}



void input_case()//每一個(gè)case的輸入函數(shù)
{

    
int i;
    
for(i=1;i<=m;i++)
    
{
        node 
*p;
        node 
*q;
        
int a,b,c;
        scanf(
"%d%d%d",&a,&b,&c);
        
////////////////////////
        p=&edge[a];
        q
=new node;
        q
->v=b;
        q
->w=c;
        q
->next=p->next;
        p
->next=q;
        
////////////////////////
        p=&reversed_edge[b];
        q
=new node;
        q
->v=a;
        q
->w=c;
        q
->next=p->next;
        p
->next=q;
    }

}



void spfa(node edge[])//SPFA部分
{

    
int i;
    
///////////////////////////////////////////////////////////////
    memset(mark,false,sizeof(mark));
    
for(i=1;i<=n;i++)
        dis[i]
=MAX_NUM;
    
while(myqueue.size()!=0)
        myqueue.pop();
    
///////////////////////////////////////////////////////////
    dis[1]=0;
    mark[
1]=true;
    myqueue.push(
1);
    
while(myqueue.size()!=0)//如果隊(duì)列不空,則進(jìn)行松弛操作,直到隊(duì)列空為止
    {
        
int temp=myqueue.front();
        myqueue.pop();
        mark[temp]
=false;
        node 
*p;
        
for(p=edge[temp].next;p!=NULL;p=p->next)
        
{
            
if(dis[p->v]>dis[temp]+p->w)
            
{
                dis[p
->v]=dis[temp]+p->w;
                
if(mark[p->v]!=true)
                
{
                    myqueue.push(p
->v);
                    mark[p
->v]=true;
                }

            }

        }

    }

}



int main()
{

    
int testcase;
    
int i,j;
    __int64 sum;
    scanf(
"%d",&testcase);
    
for(i=1;i<=MAX_DOTNUM-1;i++)
    
{
        edge[i].v
=i;
        edge[i].w
=0;
        edge[i].next
=NULL;
    }

    
for(i=1;i<=MAX_DOTNUM-1;i++)
    
{
        reversed_edge[i].v
=i;
        reversed_edge[i].w
=0;
        reversed_edge[i].next
=NULL;
    }

    
for(i=1;i<=testcase;i++)
    
{
        sum
=0;
        scanf(
"%d%d",&n,&m);
        initial(edge);
        initial(reversed_edge);
        input_case();
        spfa(edge);
        
for(j=1;j<=n;j++)
            sum
+=dis[j];
        spfa(reversed_edge);
        
for(j=1;j<=n;j++)
            sum
+=dis[j];
        printf(
"%I64d\n",sum);
    }

    system(
"pause");
    
return 0;

}


posted on 2009-04-11 00:51 abilitytao 閱讀(2814) 評(píng)論(2)  編輯 收藏 引用

評(píng)論

# re: POJ 1511-Invitation Cards(SPFA算法) 2009-04-12 12:25 lzmagic

嘿嘿,寫(xiě)得真不錯(cuò),我的用STL超時(shí)了~
貌似把
initial(edge);
initial(reversed_edge);
這兩句放到
printf("%I64d\n",sum);
后面去會(huì)超時(shí),也許是最后一句數(shù)據(jù)釋放要很久……  回復(fù)  更多評(píng)論   

# re: POJ 1511-Invitation Cards(SPFA算法) 2009-04-14 16:09 abilitytao

really?我試試看 我開(kāi)始還以為是回收的效率很高呢...  回復(fù)  更多評(píng)論   


只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲最新色图| 午夜视频在线观看一区二区| 久久综合九色九九| 欧美高清在线一区二区| 亚洲尤物在线视频观看| 久久精品一二三区| 亚洲一区二区三区中文字幕| 欧美在线观看一区二区| 亚洲一区欧美激情| 欧美黄色精品| 久久久久se| 国产欧美日韩一区二区三区| 亚洲人成在线免费观看| 欧美午夜在线一二页| 亚洲第一狼人社区| 在线观看亚洲视频| 亚洲第一黄网| 欧美永久精品| 久久综合九色综合欧美狠狠| 国产精品99免费看 | 欧美大片在线观看| 国产精品伦一区| 亚洲免费在线看| 亚洲自拍电影| 国产精品素人视频| 亚洲欧美日韩视频二区| 亚洲欧美日韩天堂一区二区| 欧美日韩一区二区三区在线观看免 | 久久99伊人| 狠狠入ady亚洲精品| 久久精品国产综合| 欧美第十八页| 在线午夜精品| 国产精品稀缺呦系列在线| 欧美在线国产| 99视频精品免费观看| 欧美在线网站| 日韩一级视频免费观看在线| 国产精品理论片| 久久综合九色综合久99| 亚洲深夜福利视频| 亚洲国产精品精华液2区45| 中文精品一区二区三区| 国产曰批免费观看久久久| 欧美国产日韩亚洲一区| 久久福利精品| 欧美一级二区| 99国产精品久久久久老师| 久久综合中文字幕| 亚洲与欧洲av电影| 亚洲欧洲一级| 18成人免费观看视频| 国产九九视频一区二区三区| 欧美精品在线观看一区二区| 久久久久国内| 亚洲午夜av在线| 亚洲靠逼com| 亚洲三级视频| 一区二区国产精品| 一本高清dvd不卡在线观看| 亚洲国产精品热久久| 在线欧美电影| 亚洲伦理在线免费看| 亚洲精品视频一区| 亚洲精品一区二区三区在线观看 | 欧美主播一区二区三区美女 久久精品人| 亚洲精品网址在线观看| 在线观看国产欧美| 亚洲伦理精品| 欧美一级精品大片| 久久久久久伊人| 亚洲日本欧美在线| 亚洲精品麻豆| 久久国产精品电影| 美女啪啪无遮挡免费久久网站| 久久躁日日躁aaaaxxxx| 欧美精品www在线观看| 国产美女一区| 一区二区三区四区蜜桃| 欧美在线视频a| 99热精品在线观看| 免费日韩av| 精品动漫3d一区二区三区免费 | 一区二区三区在线观看欧美| 亚洲精品一线二线三线无人区| 亚洲一区二区精品| 狼人社综合社区| 亚洲性人人天天夜夜摸| 你懂的视频欧美| 欲色影视综合吧| 欧美一区三区三区高中清蜜桃| 美女图片一区二区| 欧美一区国产二区| 在线中文字幕不卡| 欧美专区亚洲专区| 欧美va亚洲va香蕉在线| 久久亚洲综合色一区二区三区| 亚洲国产一区二区在线| 亚洲人永久免费| 国内精品久久久久影院色| 亚洲一区二区三区欧美| 亚洲国产高清aⅴ视频| 欧美高清在线一区二区| 亚洲欧美日韩爽爽影院| 欧美日韩一区二区高清| 久久久久se| 免费人成精品欧美精品| 亚洲人成网站精品片在线观看| 欧美aⅴ一区二区三区视频| 久久午夜羞羞影院免费观看| 亚洲第一精品夜夜躁人人躁| 欧美国产另类| 国产精品福利av| 午夜视频在线观看一区二区三区| 国语自产偷拍精品视频偷| 亚洲精品美女久久久久| 亚洲国产精品va在线看黑人动漫| 亚洲新中文字幕| 99riav久久精品riav| 久久精品亚洲一区二区| 亚洲一区二区三区国产| 久久一区二区三区四区五区| 亚洲女人天堂成人av在线| 麻豆国产精品va在线观看不卡| 欧美一区二区三区久久精品| 欧美日韩国产一区| 欧美国产日产韩国视频| 国产资源精品在线观看| 亚洲一区影音先锋| 亚洲一区二区在线| 欧美国产国产综合| 91久久久久| 日韩一区二区久久| 欧美日韩中文在线观看| 久久色在线观看| 久久精品久久综合| 亚洲日本中文字幕| 久久国产精品久久久| 99精品久久免费看蜜臀剧情介绍| 国产精品黄视频| 久久久亚洲影院你懂的| 欧美日韩一区在线观看视频| 亚洲欧美一级二级三级| 久久久久久夜| 亚洲精品美女久久久久| 欧美日韩国产精品专区| 午夜精品久久久久久久久久久久久| 亚洲一区二区在线免费观看| 国产欧美一区二区精品忘忧草 | 欧美一区二区精品| 欧美电影电视剧在线观看| 亚洲看片免费| 国产精品一二三四| 欧美电影免费观看网站| 久久成年人视频| 亚洲综合精品一区二区| 免费美女久久99| 久久精品99国产精品日本| 亚洲综合视频网| 亚洲一区在线看| 亚洲影院色无极综合| 日韩视频专区| 亚洲三级免费| 99精品免费| 亚洲丁香婷深爱综合| 国产一区二区三区在线观看网站| 免费毛片一区二区三区久久久| 午夜精品久久久久久久久久久久| 日韩视频精品| 亚洲欧美日韩中文视频| 亚洲欧美日韩国产综合| 一区二区三区精品在线 | 国产综合18久久久久久| 欧美日韩三级| 国产精品久在线观看| 国产精品一区一区三区| 国产精品综合不卡av| 在线观看国产精品网站| 99视频在线观看一区三区| 亚洲欧美中文在线视频| 你懂的国产精品永久在线| 9l视频自拍蝌蚪9l视频成人| 久久久国产一区二区三区| 欧美日韩亚洲激情| 亚洲福利在线看| 欧美专区日韩视频| 亚洲人成艺术| 亚洲精品无人区| 日韩午夜激情电影| 亚洲片国产一区一级在线观看| 亚洲欧美一区二区三区久久| 亚洲无吗在线| 99国产精品久久久| 午夜日本精品| 欧美成人免费全部| 国产一区二区三区久久精品| 99国产精品视频免费观看一公开 | 久久精品人人爽| 一本色道久久综合亚洲精品按摩| 久久久欧美精品sm网站|