O(1) 的小乐

Job Hunting

公告

记录我的生活和工作。。。
<2010年9月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

统计

  • 随笔 - 182
  • 文章 - 1
  • 评论 - 41
  • 引用 - 0

留言簿(10)

随笔分类(70)

随笔档案(182)

文章档案(1)

如影随形

搜索

  •  

最新随笔

最新评论

阅读排行榜

评论排行榜

POJ 3159 SPFA

给定一个图,(V  3*10^4, E 1.5*10^5),如此大规模的图,求一个最短路,只能使用SPFA(使用栈进行优化)

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 阅读(374) 评论(0)  编辑 收藏 引用 所属分类: Algorithm


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


统计系统