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

            POJ 1062 Java (圖論)

            //仿照別人的思想敲得,之前不是很了解dijkstra,做過這題后有些理解
            //1,將當前未納入最短路的符合要求的距離最短結點納入最短路;
            //2,將所有與當前納入的結點有關聯并且未被納入最短路的結點最短距離進行更新。
            //圖論中另一個求最小生成樹的的經典算法Prim算法與Dij過程極其類似,都是貪心思想。
            //只是一個是對頂點的選擇,另外一個是對邊的選擇。

            import java.util.*;
            public class Main
            { public static int[][] e;
               public static int[]  dis;
               public static int[] used;
               public static int[] level;
               public static int n,m;
               public static void main(String[] args){
                Scanner cin = new Scanner(System.in);
                int  x,t;
                e = new int[101][101];
                dis = new int[101];
                used =  new int[101];
                level = new int[101];
                      m=cin.nextInt();
                      n=cin.nextInt();
                       for(int i=1;i<=n;i++)
                         {   e[0][i]=cin.nextInt();
                             level[i]=cin.nextInt();
                              x=cin.nextInt();
                            for(int j=0;j<x;j++)
                            { t=cin.nextInt();
                              e[t][i]=cin.nextInt();
                            }
                         }
                       solve();
            }

            public static void solve()
            { int max,result;
              result=e[0][1];
              for(int i=1;i<=n;i++)
                 { max=level[i];
                   for(int j=1;j<=n;j++)
                    if(level[j]>max || level[j]<max-m)//判斷所交易的人的等級是否符合題目所述的條件
                     used[j]=1;//不符合
                    else
                     used[j]=0; //符合
                   dijkstra();
                   if(result>dis[1]) //比較每次所求的費用
                     result=dis[1];
            }
            System.out.println(result);
            }
            public static void dijkstra()
            { int min,temp,k;
              for(int i=1;i<=n;i++)
               dis[i]=e[0][i];
              for(int i=1;i<=n;i++)
                 { min=0x7FFFFFFF;
                   k=0;
                   for(int j=1;j<=n;j++)//找出代價最小的邊
                     if(used[j]==0 && dis[j]<min)
                      {min=dis[j];
                          k=j;
                      }
                   if(k==0)
                    break;
                   used[k]=1;
                   for(int j=1;j<=n;j++)//更新其節點的值
                    if(used[j]==0 && e[k][j]>0 && min+e[k][j]<dis[j])
                     dis[j]=min+e[k][j];
                }
               }
            }

            posted on 2008-11-27 00:20 蝸牛 閱讀(1725) 評論(0)  編輯 收藏 引用 所屬分類: ACM ICPC

            <2008年11月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            30123456

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆分類(20)

            隨筆檔案(20)

            Favorites

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            精品国产青草久久久久福利 | …久久精品99久久香蕉国产| 精品国产乱码久久久久软件| 人妻少妇久久中文字幕一区二区| 国产午夜免费高清久久影院| 久久精品国产99久久久香蕉| 久久人人爽人人爽人人爽| 久久国产热精品波多野结衣AV| 色综合色天天久久婷婷基地| 一本大道久久东京热无码AV | 国产精品久久免费| 色欲综合久久躁天天躁| 久久久久国产精品熟女影院| 人妻无码久久精品| 久久九九有精品国产23百花影院| 亚洲精品美女久久久久99小说| 99久久国产热无码精品免费| 一本色道久久88综合日韩精品 | 亚洲欧洲精品成人久久曰影片 | 久久婷婷国产麻豆91天堂| 一级做a爰片久久毛片看看| 久久精品国产亚洲AV嫖农村妇女| 亚洲伊人久久成综合人影院| 伊人久久精品线影院| 国产精品9999久久久久| 伊人色综合久久天天人手人婷| 久久男人中文字幕资源站| 久久精品草草草| 久久99热狠狠色精品一区| 国产成人久久精品一区二区三区 | 日韩中文久久| 久久九九久精品国产免费直播| 美女写真久久影院| 亚洲一区中文字幕久久| 久久噜噜电影你懂的| 国产精品久久久久9999高清| 久久男人Av资源网站无码软件| 亚洲成色www久久网站夜月| 久久中文字幕人妻丝袜| 久久久久亚洲AV无码专区首JN| 久久久噜噜噜久久中文字幕色伊伊|