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

O(1) 的小樂

Job Hunting

公告

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

統(tǒng)計(jì)

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

留言簿(10)

隨筆分類(70)

隨筆檔案(182)

文章檔案(1)

如影隨形

搜索

  •  

最新隨筆

最新評論

閱讀排行榜

評論排行榜

POJ 3169 差分約束方程

一道簡單的差分約束方程,差分約束方程由Bellmanford轉(zhuǎn)換而來,一組差分方程由 x-y <=d 的形式,而在最短路中松弛條件有dis(x)<= dis(y)+w。 所以產(chǎn)生了一條由y連向x的有向邊,權(quán)重為d。

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

   1:   
   2:  #include <queue>
   3:  #include <iostream>
   4:  #include <string.h>
   5:  #include <stdio.h>
   6:  using namespace std;
   7:  #define MAXN 1005      // vertex
   8:  #define MAXM 20005      // edge
   9:  #define INF 0x3F3F3F3F
  10:   
  11:  struct node
  12:  {
  13:      int v, w, next;
  14:  }pnt[MAXM];
  15:   
  16:  int head[MAXN];
  17:  int  dis[MAXN];
  18:  bool vis[MAXN];
  19:  int  cnt[MAXN];       // the number of the operation of push to Quque. negatvie cycle.
  20:  int num = 0;          // the index of the edge
  21:  int N ;               // the number of the vertex.
  22:  int M ;               // the number of edges
  23:  int src, sink;
  24:  void addedge(int  u, int v, int w)
  25:  {
  26:      pnt[num].v = v; pnt[num].w= w;
  27:      pnt[num].next = head[u]; head[u] = num++;
  28:  }
  29:   
  30:  int SPFA()
  31:  {
  32:      for(int i=0; i<=N; i++)
  33:      {
  34:          vis[i]=0; dis[i] = INF; cnt[i] = 0;
  35:      }
  36:   
  37:      queue<int> Q;
  38:      Q.push(src); vis[src] = 1; dis[src] = 0; ++cnt[src]; 
  39:      while(!Q.empty()) 
  40:      {
  41:          int u = Q.front(); Q.pop();  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]) {Q.push(v); vis[v] = 1;}
  49:                  if( ++cnt[v] > N) return -1; // negative cycle.
  50:              }
  51:          }
  52:      }
  53:      if(dis[sink] == INF) return -2; // can't from src to sink.
  54:      return dis[sink];
  55:  }
  56:   
  57:  int main()
  58:  {
  59:      int ml,md;
  60:      while(scanf("%d%d%d", &N , &ml, &md)!= EOF)
  61:      {
  62:          num = 0;
  63:          memset(head, -1, sizeof(head)); 
  64:          int a, b, c;
  65:          for(int i=0; i<ml; i++)
  66:          {
  67:              scanf("%d%d%d", &a, &b, &c);
  68:              if(a>b) swap(a,b);
  69:              addedge(a, b,c);
  70:          }
  71:          for(int i=0; i<md; i++)
  72:          {
  73:              scanf("%d%d%d", &a, &b, &c);
  74:              if(a<b) swap(a,b);
  75:              addedge(a, b, -c);
  76:          }
  77:          src = 1; sink = N;
  78:          printf("%d\n", SPFA());
  79:      }
  80:      return 0;
  81:  }
.csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; }

posted on 2012-11-09 21:38 Sosi 閱讀(665) 評論(0)  編輯 收藏 引用


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


統(tǒng)計(jì)系統(tǒng)
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            欧美顶级少妇做爰| 久久精品成人一区二区三区| 欧美伦理影院| 中日韩午夜理伦电影免费| 亚洲精品在线看| 国产精品高潮呻吟久久| 午夜欧美精品久久久久久久| 欧美在线高清| 亚洲欧洲在线看| 一本久道久久综合中文字幕| 国产精品白丝黑袜喷水久久久| 午夜精品久久99蜜桃的功能介绍| 亚洲欧美综合精品久久成人| 极品日韩久久| 亚洲另类黄色| 国产亚洲欧美一区二区三区| 免费在线视频一区| 欧美日韩一二三四五区| 久久久999精品| 欧美激情亚洲激情| 欧美在线视频不卡| 欧美国产视频日韩| 欧美一区二区在线看| 免费黄网站欧美| 香蕉乱码成人久久天堂爱免费| 久久久精彩视频| 这里只有精品在线播放| 欧美在线视频免费观看| 一本一道久久综合狠狠老精东影业 | 国产精品亚洲一区| 猛干欧美女孩| 国产精品入口尤物| 亚洲欧洲一区二区三区久久| 国产伦精品一区二区三区视频黑人| 欧美r片在线| 国产亚洲欧美一区二区| 日韩一级欧洲| 亚洲精品黄网在线观看| 欧美一区二区三区播放老司机 | 欧美性色视频在线| 欧美国产视频在线| 国产一区二区中文| 亚洲一区二区在线| 这里是久久伊人| 欧美a级大片| 欧美成人精品不卡视频在线观看| 欧美体内谢she精2性欧美| 欧美国产精品va在线观看| 国模 一区 二区 三区| 这里只有精品视频| 亚洲视频www| 欧美揉bbbbb揉bbbbb| 亚洲激情影视| 亚洲区中文字幕| 免费久久99精品国产| 欧美不卡在线| 亚洲国产女人aaa毛片在线| 久久精品国产精品| 久久亚洲国产精品日日av夜夜| 国产欧美一区二区精品秋霞影院| 一二美女精品欧洲| 亚洲天堂成人| 国产精品九九| 亚洲欧美视频| 久久久国产精品亚洲一区| 国产三级精品三级| 欧美中文字幕第一页| 久久精品国产99国产精品澳门| 国产精品日日摸夜夜添夜夜av | 久久亚洲欧美国产精品乐播| 国产一区99| 久久精品官网| 免费视频一区二区三区在线观看| 在线成人亚洲| 欧美二区在线播放| 一区二区三区国产盗摄| 午夜欧美精品久久久久久久| 国产麻豆精品theporn| 香港成人在线视频| 老鸭窝91久久精品色噜噜导演| 亚洲国产另类久久精品| 欧美金8天国| 亚洲天堂久久| 开心色5月久久精品| 亚洲精品一区二区在线观看| 欧美视频一区二区在线观看| 亚洲综合色网站| 玖玖视频精品| 亚洲午夜女主播在线直播| 国产精品最新自拍| 久久综合福利| 亚洲视频一区在线| 美女图片一区二区| 一级成人国产| 国语自产偷拍精品视频偷| 欧美精品久久一区| 性感少妇一区| 亚洲精品日本| 久久综合激情| 亚洲午夜免费福利视频| 激情综合电影网| 国产精品国产馆在线真实露脸| 午夜一区二区三区在线观看| 亚洲国产精品日韩| 欧美一区二区三区四区夜夜大片 | 亚洲视频在线观看一区| 国产亚洲精品久| 欧美日韩成人网| 久久成人免费网| 亚洲天堂激情| 亚洲日本激情| 老司机凹凸av亚洲导航| 亚洲欧美日韩区 | 欧美深夜影院| 奶水喷射视频一区| 久久国产精品毛片| 亚洲午夜在线视频| 亚洲剧情一区二区| 欧美激情国产高清| 久热精品视频在线观看一区| 亚洲欧洲av一区二区| 亚洲乱码精品一二三四区日韩在线 | 国产欧美日韩一区二区三区在线| 欧美精品xxxxbbbb| 蜜臀va亚洲va欧美va天堂| 亚洲欧美一区二区精品久久久| 亚洲人被黑人高潮完整版| 免费成人网www| 玖玖综合伊人| 久久免费视频观看| 久久免费视频一区| 久久精品成人欧美大片古装| 亚洲综合另类| 亚洲一区在线免费| 亚洲一区二区三区在线看| 99热这里只有精品8| 99re6这里只有精品| 亚洲精品一区二区三区在线观看| 亚洲国产精品久久久久秋霞蜜臀| 狠狠入ady亚洲精品| 狠狠色2019综合网| 在线观看中文字幕不卡| 激情亚洲网站| 在线精品视频一区二区三四| 有码中文亚洲精品| 亚洲黄网站黄| 在线亚洲观看| 欧美一级片在线播放| 久久国产精品亚洲va麻豆| 久久精品1区| 蜜臀va亚洲va欧美va天堂| 免费一级欧美片在线观看| 欧美刺激性大交免费视频| 亚洲国产精品精华液网站| 国户精品久久久久久久久久久不卡| 国产欧美日韩三区| 曰本成人黄色| 一二三四社区欧美黄| 亚洲一区二区视频| 欧美一区二区三区免费大片| 久久久一区二区三区| 欧美1级日本1级| 91久久国产精品91久久性色| 一区二区三区精品| 欧美一级理论片| 欧美不卡在线视频| 欧美性jizz18性欧美| 狠狠色狠狠色综合| 亚洲精品国产精品乱码不99按摩| 夜夜嗨av一区二区三区四季av| 亚洲在线成人精品| 老司机亚洲精品| 亚洲美女福利视频网站| 亚洲综合色噜噜狠狠| 久久综合九色综合网站| 欧美色123| 狠狠综合久久| 亚洲香蕉在线观看| 欧美成人资源| 亚洲永久免费观看| 欧美韩日一区二区| 激情成人综合| 亚洲免费在线视频| 亚洲二区在线观看| 午夜日韩av| 欧美日韩一区二区在线观看视频 | 国产区在线观看成人精品| 亚洲黄色性网站| 欧美在线视频导航| 日韩午夜中文字幕| 蜜桃av一区二区三区| 国产欧美一区二区三区国产幕精品 | 亚洲资源av| 亚洲激情综合| 久久精品欧美| 国产人成一区二区三区影院| 99精品国产在热久久婷婷| 米奇777在线欧美播放| 亚洲在线观看免费| 欧美日韩精品中文字幕|