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

公告

記錄我的生活和工作。。。
<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

統(tǒng)計(jì)

  • 隨筆 - 182
  • 文章 - 1
  • 評(píng)論 - 41
  • 引用 - 0

留言簿(10)

隨筆分類(lèi)(70)

隨筆檔案(182)

文章檔案(1)

如影隨形

搜索

  •  

最新隨筆

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

POJ 3268

求從原點(diǎn)到達(dá)某個(gè)點(diǎn)之后返回,來(lái)回最長(zhǎng)的距離是多少? 比較基礎(chǔ)的問(wèn)題,兩遍Dijkstra就可以了。

   1:   
   2:  #include <iostream> 
   3:  #include <vector>
   4:  #include <algorithm>
   5:  #include <queue>
   6:  #include <string.h>
   7:  #include <stdio.h>
   8:  using namespace std;
   9:   
  10:  #define V   1005
  11:  #define E   100005
  12:  #define INF 329999         
  13:   
  14:  // v :the end point of an edge. w : the weight of the weight next:cluster according to the begin point of the edge
  15:  struct node
  16:  {
  17:      int v, w,next;
  18:      node(int vv=0, int ww=0):v(vv),w(ww){}
  19:      bool operator < (const node& r) const{return w> r.w;}
  20:  }pnt[E],pnt1[E];
  21:   
  22:  int e=0,N,M,s;
  23:   
  24:  int head[V];
  25:  int dis[V];
  26:  bool vis[V];
  27:  int src, sink;
  28:   
  29:  void Dijkstra()
  30:  { 
  31:      priority_queue<node> Q; 
  32:      vis[src] = 1; dis[src] = 0; 
  33:      Q.push(node(src, 0)); 
  34:      for (int u = src, i=1; i< N; i++)                 
  35:      { 
  36:          for (int j = head[u]; j != -1; j = pnt[j].next)    // j is edge number.
  37:          { 
  38:              int v = pnt[j].v;                          
  39:              if (vis[v] == 0 && dis[v] > dis[u] + pnt[j].w )// pre is the current vertex
  40:              { 
  41:                  dis[v] = dis[u] + pnt[j].w; 
  42:                  Q.push(node(v, dis[v]));
  43:              } 
  44:          } 
  45:          while (!Q.empty() && vis[Q.top().v]) Q.pop(); 
  46:          if (Q.empty()) break;
  47:          vis[u = Q.top().v] = 1; Q.pop();
  48:      }
  49:  } 
  50:  int head1[V];
  51:  inline void addedge1(int u, int v, int w)
  52:  {
  53:      pnt1[s].v =v; pnt1[s].w = w; pnt1[s].next = head1[u]; head1[u]=s++;
  54:  }
  55:  inline void addedge(int u, int v, int w){ 
  56:      pnt[e].v = v; pnt[e].w = w; pnt[e].next= head[u]; head[u]=e++;
  57:  } 
  58:   
  59:  void Dijkstra_init()
  60:  { 
  61:      e = 0; s =0;
  62:      memset(head, -1, sizeof(head)); 
  63:      memset(head1, -1, sizeof(head));
  64:      memset(vis, 0, sizeof(vis));
  65:      scanf("%d%d", &N , &M);
  66:      for (int i = 0; i <=N; i++) dis[i] = INF; 
  67:      scanf("%d", &src);
  68:      //cout<<src<<endl;
  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:          addedge1(b,a, c);
  75:      }
  76:   
  77:   
  78:  } 
  79:   
  80:  int main()
  81:  {
  82:      //freopen("3268.txt","r",stdin);
  83:   
  84:      Dijkstra_init();
  85:      Dijkstra();
  86:      int dis1[V];
  87:      for(int i=0; i<=N; i++) dis1[i] = dis[i];
  88:      //for(int i=1; i<=N; i++) cout<<dis[i]<<" "; cout<<endl;
  89:      memset(vis, 0 ,sizeof(vis));
  90:      for(int i=0; i<=N; i++) { dis[i]= INF; head[i] = head1[i];}
  91:      for(int i=0; i<M; i++)
  92:      {
  93:          pnt[i]=pnt1[i];
  94:   
  95:      }
  96:      Dijkstra();
  97:      //for(int i=1; i<=N; i++) cout<<dis[i]<<" "; cout<<endl;
  98:      int ret = 0;
  99:      for(int i=1; i<=N; i++) ret = max(ret, dis1[i]+dis[i]);
 100:      cout<<ret<<endl;
 101:      return 0;
 102:  }
 103:   

posted on 2012-11-10 00:03 Sosi 閱讀(470) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): Algorithm

統(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综合在线| 国产精品热久久久久夜色精品三区| 国产精品久久久久久久久免费桃花| 一本色道久久综合亚洲精品不卡 | 亚洲欧美综合v| 亚洲一区999| 狠狠色伊人亚洲综合成人| 免费成人高清视频| 欧美久久视频| 欧美在线观看天堂一区二区三区| 久久精品亚洲一区二区| 亚洲国产欧美在线人成| 亚洲美女色禁图| 国产日韩一区欧美| 欧美成人午夜激情视频| 欧美日韩国产色视频| 欧美在线视频观看免费网站| 久久久久一区| 国产精品99久久久久久www| 亚洲一区二区免费| 亚洲激情影视| 午夜精品国产精品大乳美女| 亚洲国产精品高清久久久| aa日韩免费精品视频一| 激情综合视频| 日韩一级精品视频在线观看| 国内精品久久久久久影视8| 亚洲人体大胆视频| 国产视频在线观看一区| 亚洲欧洲精品一区二区三区| 国产一区二区av| 亚洲精品一区二区三| 激情综合久久| 亚洲综合二区| 一区二区三区四区国产精品| 久久久精品国产一区二区三区 | 亚洲成人在线视频播放| 一区二区三区黄色| 亚洲黄色尤物视频| 欧美一级黄色网| 亚洲性xxxx| 免费不卡中文字幕视频| 久久国产精品一区二区三区四区| 欧美日韩精品久久久| 美乳少妇欧美精品| 国产亚洲第一区| 亚洲无线视频| 亚洲先锋成人| 欧美日韩国产在线播放网站| 欧美国产日韩一区二区| 在线精品视频一区二区三四| 亚洲欧美国产77777| 亚洲一区二区av电影| 欧美激情无毛| 亚洲人成在线观看网站高清| 亚洲欧洲一区二区三区在线观看 | 亚洲国产va精品久久久不卡综合| 激情欧美日韩一区| 久久久精品网| 麻豆精品网站| 在线看无码的免费网站| 久久精品国产亚洲aⅴ| 久久久久久9| 精久久久久久| 免费日韩av| 亚洲国产精品久久久久婷婷884| 亚洲国产精品久久久久婷婷884 | 欧美午夜在线观看| 亚洲午夜免费视频| 午夜视黄欧洲亚洲| 国产视频观看一区| 欧美一区影院| 欧美成人午夜免费视在线看片| 国内激情久久| 免费日韩视频| 日韩一级欧洲| 欧美一区在线看| 影音先锋欧美精品| 免费欧美日韩| 中日韩男男gay无套| 久久精品国产成人| 亚洲二区视频| 欧美午夜片在线观看| 亚洲天堂免费在线观看视频| 久久国产高清| 亚洲精品乱码| 国产精品视频成人| 久久伊人精品天天| 亚洲免费精彩视频| 欧美在线观看www| 亚洲第一黄色网| 欧美视频在线免费| 性欧美videos另类喷潮| 欧美大片一区| 午夜欧美视频| 亚洲国产一区二区视频| 国产精品久久精品日日| 久久人人爽国产| av成人黄色| 久久夜色精品国产亚洲aⅴ | 亚洲国产精品精华液网站| 欧美三级电影网| 久久人人精品| 亚洲欧美久久久久一区二区三区| 欧美电影免费观看| 欧美在线视频观看免费网站| 亚洲日本aⅴ片在线观看香蕉| 欧美性猛交xxxx乱大交蜜桃| 久久久久久综合| 这里只有精品视频| 欧美激情aaaa| 久久婷婷蜜乳一本欲蜜臀| 中文国产成人精品| 亚洲第一黄网| 国产一区二区三区在线播放免费观看| 欧美激情一区| 裸体一区二区三区| 久久www成人_看片免费不卡| 亚洲精品一区二区三区不| 欧美成人午夜激情在线| 久久久水蜜桃| 久久国产色av| 亚洲欧美日韩综合国产aⅴ| 亚洲精品人人| 亚洲国产精品999| 精品999日本| 国产三区精品| 国产亚洲a∨片在线观看| 国产精品乱人伦中文| 欧美日韩一级视频| 欧美精品尤物在线| 欧美好骚综合网| 欧美精品18videos性欧美| 久热精品视频| 久久夜色精品国产| 久久一二三国产| 蜜桃伊人久久| 欧美高清不卡| 欧美二区视频| 欧美精品在线免费| 欧美区日韩区| 欧美偷拍一区二区| 国产精品国产三级国产aⅴ无密码| 欧美精品日韩一本| 欧美日韩综合在线| 国产精品免费看久久久香蕉| 国产精品成人在线| 国产精品一区二区三区四区五区| 欧美亚州一区二区三区 | 欧美日韩中文在线观看| 欧美日韩在线播放三区四区| 国产精品白丝av嫩草影院| 国产精品高清网站| 国产精品系列在线| 极品少妇一区二区三区| 在线免费观看视频一区| 最新日韩欧美| 亚洲一区二区三区四区中文| 午夜视频一区二区| 久热综合在线亚洲精品| 欧美国产日韩视频| 99xxxx成人网| 欧美中文在线观看国产| 六十路精品视频| 欧美视频在线播放| 一区久久精品| 一区二区高清视频| 久久成人一区| 亚洲大胆在线| 亚洲一区二区三区四区在线观看| 欧美在线观看一区二区| 欧美不卡激情三级在线观看| 欧美性大战久久久久| 激情小说另类小说亚洲欧美| 99精品欧美一区二区蜜桃免费| 午夜精品视频一区| 免费永久网站黄欧美| 一区二区三区蜜桃网| 久久久美女艺术照精彩视频福利播放| 欧美精品久久一区二区| 国产日韩亚洲欧美精品| 亚洲乱码日产精品bd| 久久大逼视频| 亚洲久久成人| 久久久久国内| 国产精品欧美经典| 亚洲精品美女免费| 久久久精品2019中文字幕神马| 亚洲激情成人| 久久精品国产一区二区三| 欧美视频一区| 亚洲每日更新| 免费欧美日韩国产三级电影| 亚洲一区成人| 国产精品av久久久久久麻豆网| 亚洲国产免费| 久久久五月天|