• <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>

            O(1) 的小樂

            Job Hunting

            公告

            記錄我的生活和工作。。。
            <2011年5月>
            24252627282930
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            統(tǒng)計

            • 隨筆 - 182
            • 文章 - 1
            • 評論 - 41
            • 引用 - 0

            留言簿(10)

            隨筆分類(70)

            隨筆檔案(182)

            文章檔案(1)

            如影隨形

            搜索

            •  

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            POJ 3159 SPFA

            給定一個圖,(V  3*10^4, E 1.5*10^5),如此大規(guī)模的圖,求一個最短路,只能使用SPFA(使用棧進(jìn)行優(yōu)化)

            https://github.com/Sosi/ProgrammingContest/blob/master/OnlineJudge/POJ/PKU3159.cpp

               1:  #include <queue>
               2:  #include <iostream>
               3:  #include <string.h>
               4:  #include <stdio.h>
               5:  using namespace std;
               6:  #define MAXN 30010      // vertex
               7:  #define MAXM 150010      // edge
               8:  #define INF 0x3F3F3F3F
               9:   
              10:  struct node
              11:  {
              12:      int v, w, next;
              13:  }pnt[MAXM];
              14:   
              15:  int head[MAXN];
              16:  int  dis[MAXN];
              17:  bool vis[MAXN];
              18:  int  cnt[MAXN];       // the number of the operation of push to Quque. negatvie cycle.
              19:  int num = 0;          // the index of the edge
              20:  int N ;               // the number of the vertex.
              21:  int M ;               // the number of edges
              22:  int src, sink;
              23:  void addedge(int  u, int v, int w)
              24:  {
              25:      pnt[num].v = v; pnt[num].w= w;
              26:      pnt[num].next = head[u]; head[u] = num++;
              27:  }
              28:   
              29:  int SPFA()
              30:  {
              31:      for(int i=0; i<=N; i++)
              32:      {
              33:          vis[i]=0; dis[i] = INF; cnt[i] = 0;
              34:      }
              35:   
              36:      int Q[MAXM], top=1;
              37:      Q[0] = src; vis[src] = 1;
              38:      dis[src] = 0;
              39:      while(top)
              40:      {
              41:          int u = Q[--top]; vis[u] = 0;
              42:          for(int i = head[u]; i!=-1; i=pnt[i].next)
              43:          {
              44:              int v = pnt[i].v;
              45:              if(dis[v]> dis[u] + pnt[i].w )
              46:              {
              47:                  dis[v]= dis[u] +pnt[i].w;
              48:                  if(!vis[v])
              49:                  {
              50:                      Q[top++] = v; vis[v]= 1;
              51:                  }
              52:              }
              53:   
              54:          }
              55:      }
              56:   
              57:   
              58:   
              59:      return dis[sink];
              60:  }
              61:   
              62:  int main()
              63:  {
              64:      //freopen("3159.txt", "r", stdin);
              65:      while(scanf("%d%d", &N , &M)!= EOF)
              66:      {
              67:          num = 0;
              68:          memset(head, -1, sizeof(head)); 
              69:          for(int i=0; i<M; i++)
              70:          {
              71:              int a, b, c;
              72:              scanf("%d%d%d", &a, &b, &c);
              73:              addedge(a, b,c);
              74:          }
              75:          //cout<<num<<endl;
              76:          src = 1; sink = N;
              77:          //cout<<"src "<<src<<" sink "<<N<<endl;
              78:          printf("%d\n", SPFA());
              79:      }
              80:      return 0;
              81:  }

            posted on 2012-11-09 21:15 Sosi 閱讀(393) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm

            統(tǒng)計系統(tǒng)
            久久综合久久综合亚洲| 久久99精品国产| 亚洲国产一成人久久精品| 中文字幕日本人妻久久久免费| 久久国产精品无| 久久精品国产半推半就| 久久国产AVJUST麻豆| av国内精品久久久久影院| 青青草原综合久久大伊人导航| 新狼窝色AV性久久久久久| 国内精品久久久久久不卡影院| 日本WV一本一道久久香蕉| 国产成人精品久久一区二区三区av| 青春久久| 久久综合视频网站| 久久久精品免费国产四虎| 亚洲乱码中文字幕久久孕妇黑人| 久久性精品| 狠狠色综合久久久久尤物| 久久综合香蕉国产蜜臀AV| 欧美一区二区久久精品| 精品水蜜桃久久久久久久| 国产精品一久久香蕉产线看| 香蕉久久夜色精品升级完成| 亚洲乱码日产精品a级毛片久久 | 久久久久久久精品妇女99| 久久精品一区二区影院| 日本免费久久久久久久网站| 国内精品久久久久久野外| 日韩av无码久久精品免费| 午夜久久久久久禁播电影| 少妇无套内谢久久久久| 久久久精品国产| 麻豆av久久av盛宴av| 狠狠色狠狠色综合久久| 亚洲色婷婷综合久久| 久久人人爽人人爽人人AV| 久久九九精品99国产精品| 久久成人影院精品777| 日本一区精品久久久久影院| 日韩精品久久久久久|