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

            公告

            記錄我的生活和工作。。。
            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            統(tǒng)計(jì)

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

            留言簿(10)

            隨筆分類(70)

            隨筆檔案(182)

            文章檔案(1)

            如影隨形

            搜索

            •  

            最新隨筆

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            POJ 3268

            求從原點(diǎn)到達(dá)某個(gè)點(diǎn)之后返回,來回最長的距離是多少? 比較基礎(chǔ)的問題,兩遍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 閱讀(462) 評(píng)論(0)  編輯 收藏 引用 所屬分類: Algorithm

            統(tǒng)計(jì)系統(tǒng)
            91久久成人免费| 国产欧美久久一区二区| 国产一区二区三区久久| 亚洲AV无码久久精品蜜桃| 热久久最新网站获取| 久久久久久久久66精品片| 日本高清无卡码一区二区久久| 国产精自产拍久久久久久蜜| 久久精品国产一区二区三区| 久久精品人妻一区二区三区| 亚洲中文字幕伊人久久无码| 波多野结衣久久精品| 久久99国产综合精品女同| 日韩亚洲欧美久久久www综合网| 成人精品一区二区久久久| 久久国产香蕉视频| 亚洲AV无码久久| 久久er99热精品一区二区| 国产免费久久精品99久久| 亚洲午夜精品久久久久久浪潮| 久久精品日日躁夜夜躁欧美| 精品久久人妻av中文字幕| 久久精品国产只有精品66 | 久久国产亚洲精品| 久久国产精品成人影院| 久久噜噜久久久精品66| 97精品国产91久久久久久| 一级女性全黄久久生活片免费| 91精品国产乱码久久久久久| 久久最新免费视频| 91精品国产色综久久| 亚洲国产精品无码成人片久久| 久久久久亚洲AV综合波多野结衣| 精品久久久久久久久午夜福利| 一本一本久久a久久精品综合麻豆| 久久99热国产这有精品| 亚洲香蕉网久久综合影视 | 久久精品国产网红主播| 久久乐国产综合亚洲精品| 国产农村妇女毛片精品久久| …久久精品99久久香蕉国产|