POJ 3311---Hie with the Pie(狀壓DP)

来源:http://www.cnblogs.com/chen9510/archive/2017/05/06/6817488.html
-Advertisement-
Play Games

題目鏈接 Description The Pizazz Pizzeria prides itself in delivering pizzas to its customers as fast as possible. Unfortunately, due to cutbacks, they can ...


題目鏈接

 

Description

The Pizazz Pizzeria prides itself in delivering pizzas to its customers as fast as possible. Unfortunately, due to cutbacks, they can afford to hire only one driver to do the deliveries. He will wait for 1 or more (up to 10) orders to be processed before he starts any deliveries. Needless to say, he would like to take the shortest route in delivering these goodies and returning to the pizzeria, even if it means passing the same location(s) or the pizzeria more than once on the way. He has commissioned you to write a program to help him.

Input

Input will consist of multiple test cases. The first line will contain a single integer n indicating the number of orders to deliver, where 1 ≤ n ≤ 10. After this will be n + 1 lines each containing n + 1 integers indicating the times to travel between the pizzeria (numbered 0) and the n locations (numbers 1 to n). The jth value on the ith line indicates the time to go directly from location i to location j without visiting any other locations along the way. Note that there may be quicker ways to go from i to j via other locations, due to different speed limits, traffic lights, etc. Also, the time values may not be symmetric, i.e., the time to go directly from location i to j may not be the same as the time to go directly from location j to i. An input value of n = 0 will terminate input.

Output

For each test case, you should output a single number indicating the minimum time to deliver all of the pizzas and return to the pizzeria.

Sample Input

3
0 1 10 10
1 0 1 2
10 1 0 10
10 2 10 0
0

Sample Output

8

題意:貌似是一個人從店裡出發送東西,把n個地方的東西送完了再回到店裡,商店及這n個地方任意兩兩之間的距離給了,即輸入的(n+1)*(n+1)的矩陣,每個點可以到多次,求走的最短路徑值;

思路:先用floyd計算兩點之間的最短距離,定義dp[s][i],s表示已經走過的點,i表示現在正位於的點,dp[s][i]的值表示走完剩餘沒到的點(及加上回商店的路徑長)所需的最短路徑長,從底層開始推到即s=1<<(n+1):0;

代碼如下:
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int inf=99999999;
int dp[2505][12];
int d[12][12];

int main()
{
    int n;
    while(scanf("%d",&n)&&n)
    {
        for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
          scanf("%d",&d[i][j]);
        for(int k=0;k<=n;k++)
        for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

        int t=1<<(n+1);
        for(int i=0;i<t;i++)
        for(int j=0;j<=n;j++)
          dp[i][j]=inf;
        dp[t-1][0]=0;
        for(int s=t-1;s>=0;s--)
            for(int i=0;i<=n;i++)
            {
                if(!(s&(1<<i))&&(s||i)) continue;
///白書上沒有這條語句,加上後可以減小運算量。為什麼呢?因為i表示當前所在點,那s狀態集合應該包含i,這樣可以減少很大一部分的計算量,但是還得考慮s=0的情況
///s=0時是為了計算走完所有應送東西的點後,加上從結束的點回商店的距離,總距離最小者即為結果。
///或者也可以直接寫if(!(s&(1<<i))) continue; 這樣就得在最後計算從結束點回商店總距離,即下麵註釋部分代碼;
for(int j=0;j<=n;j++) { if(s&(1<<j)) continue; dp[s][i]=min(dp[s][i],dp[s^(1<<j)][j]+d[j][i]); } } printf("%d\n",dp[0][0]); // int tmp=inf; // for(int i=1;i<=n;i++) // { // tmp=min(tmp,dp[(1<<i)][i]+d[i][0]); // } // printf("%d\n",tmp); } return 0; }

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 1、java程式的基本結構大體上可以分為包、類、main()主方法、標識符、關鍵字、語句和註釋等。 2、標識符和關鍵字區分大小寫。 3、主方法是應用程式的入口點,java程式是從該方法開始執行的,main是主方法的名稱,程式員不可以更改。 4、標識符 是一個名字,用來標識類名、變數名、方法名、數組名 ...
  • 看了兩天《Learn Objective-C on the MAC》 中文版本《Objective-C基礎編程》,大概認真讀到了第9章記憶體管理部分,感覺這語言可比C++簡單多了。 第一天,因為有C語言基礎的緣故,我在windows 上安裝了GNUstep (Objective-C)開發環境,變看電子 ...
  • 題目描述 為了準備一個獨特的頒獎典禮,組織者在會場的一片矩形區域(可看做是平面直角坐標系的第一象限)鋪上一些矩形地毯。一共有 n 張地毯,編號從 1 到n 。現在將這些地毯按照編號從小到大的順序平行於坐標軸先後鋪設,後鋪的地毯覆蓋在前面已經鋪好的地毯之上。 地毯鋪設完成後,組織者想知道覆蓋地面某個點 ...
  • 一、任務 後臺——登錄 包含的內容:1)bootstrap驗證--登錄 2)MD5加密(加鹽)--對密碼 3)三框架頁面--主頁面 二、整體圖 三、分享 源碼、資料庫及圖片共用鏈接:http://pan.baidu.com/s/1dFIMav3 密碼:sers ...
  • 作業二:多級菜單 1.三級菜單 2.可以次選擇進入各子菜單 3.所需新知識點:列表、字典 4.列印b回到上一層 5.列印q退出迴圈 流程圖如下: readme: (1)存儲三級菜單的字典;設置標識符active用來迴圈; (2)生成存儲省市的字典,d1 = {1: '河南', 2: '廣東', 3: ...
  • 寫在前面的話 個人由某方面的興趣需要學習 F#,網路上有關F#的中文資料很少,微軟官方有很不錯的文檔,但是很可惜的是絕大部分的章節都是英文的。個人是一位.NET愛好者,想自己將 F# 的官方文檔翻譯出來,算是為了自己喜歡的 .NET 做一些貢獻。 原文鏈接 Getting started with ...
  • 題目描述 祖瑪是一款曾經風靡全球的游戲,其玩法是:在一條軌道上初始排列著若幹 個彩色珠子,其中任意三個相鄰的珠子不會完全同色。此後,你可以發射珠子到 軌道上並加入原有序列中。一旦有三個或更多同色的珠子變成相鄰,它們就會立 即消失。這類消除現象可能會連鎖式發生,其間你將暫時不能發射珠子。 開發商最近準 ...
  • 最近點用pickPoint來計算,垂點用lastPoint計算. 一般AcDbCurve類可以用AcGe類的 getClosestPointTo 來實現計算需要的點值. 下麵是代碼示例: case AcDb::kOsModeNear: { AcGeLine3d line3d(m_ptA,m_ptC) ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...