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

            infinity

              C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
              36 隨筆 :: 0 文章 :: 25 評論 :: 0 Trackbacks

            這個題我參考了別人的解題報告,題目很容易讓人產生誤解,其實不用去求最短路,求了反而不對,
            直接用輸入中所給的兩點間的距離就行了。方法是三維DP。f[a][b][c]表示當前離起點最遠的車處在
            c位置,另外兩車分別處在a,b位置時的所需要的最少的投遞時間。那么下一個狀態只有三種可能,即
            f[a][b][c+1],即c車到了c+1處
            f[a][c][c+1],即b車到了c+1處
            f[b][c][c+1],即a車到了c+1處
            當c==(目標點時) 結束。
            采取記憶化搜索的方式。

            Source Code

            Problem: 1695 User: lovecanon
            Memory: 324K Time: 0MS
            Language: C Result: Accepted
            • Source Code
              
                  
              #include<stdio.h>
                  #include
              <string.h>
                  
              int map[31][31];
                  
              int ans[31][31][31];
                  
              int n;
                  
              int GetMin(int a,int b,int c)
                  {
                  
              int tmp=a<=b?a:b;
                  tmp
              =tmp<=c?tmp:c;
                  
              return tmp;
                  }
                  
              int solve(int a,int b,int c)
                  {
                  
              if(c==n) return 0;
                  
              if(ans[a][b][c+1]==0)  ans[a][b][c+1]=solve(a,b,c+1);
                  
              if(ans[a][c][c+1]==0)  ans[a][c][c+1]=solve(a,c,c+1);
                  
              if(ans[b][c][c+1]==0)  ans[b][c][c+1]=solve(b,c,c+1);
                  
              return GetMin(ans[a][b][c+1]+map[c][c+1],ans[a][c][c+1]+map[b][c+1],ans[b][c][c+1]+map[a][c+1]);
                  }
                  
              int main()
                  {
                  
              int cases;
                  scanf(
              "%d",&cases);
                  
              while(cases--)
                  {
                  
              int i;
                  scanf(
              "%d",&n);
                  memset(ans,
              0,sizeof(ans));
                  
              for(i=1;i<=n-1;i++)
                  {
                  
              int j;
                  
              for(j=i+1;j<=n;j++)
                  {
                  scanf(
              "%d",&map[i][j]);
                  map[j][i]
              =map[i][j];
                  }
                  }
                  printf(
              "%d\n",solve(1,1,1));
                  }
                  
              return 0;
                  }

            posted on 2008-09-20 04:02 infinity 閱讀(372) 評論(0)  編輯 收藏 引用 所屬分類: acm
            久久青青草原亚洲av无码app| 日韩一区二区久久久久久| 久久这里只有精品首页| 色诱久久久久综合网ywww| 国产日韩欧美久久| 久久天天躁狠狠躁夜夜96流白浆 | 国内精品久久久久久久影视麻豆| 久久久久国产视频电影| 久久精品国产第一区二区三区| 国产A级毛片久久久精品毛片| 免费精品久久天干天干| 99久久精品免费看国产一区二区三区 | 99久久精品免费看国产一区二区三区| 色综合久久久久久久久五月| 久久久久久国产a免费观看不卡| 无码人妻久久一区二区三区免费| 国产高潮国产高潮久久久91| 性欧美大战久久久久久久久| 性做久久久久久久久| 99久久精品免费观看国产| 久久夜色精品国产欧美乱| 久久人人爽人人爽人人片AV高清 | 日日噜噜夜夜狠狠久久丁香五月 | 中文字幕成人精品久久不卡 | 中文字幕久久亚洲一区| 久久久精品波多野结衣| 国产精品狼人久久久久影院| 国产精品久久久久国产A级| 日产精品久久久久久久性色| 久久久久久国产精品无码下载| 亚洲国产成人久久一区久久 | 国产午夜精品理论片久久影视| 久久综合综合久久综合| 国产精品99久久久精品无码| 18岁日韩内射颜射午夜久久成人| 久久亚洲精品无码aⅴ大香| 亚洲精品综合久久| 亚洲日韩中文无码久久| 国产精品久久久久久搜索| 无码国内精品久久综合88| 久久无码精品一区二区三区|