Luogu P1690 貪婪的Copy

題目描述

Copy從盧牛那裡聽說在一片叫yz的神的領域埋藏著不少寶藏，於是Copy來到了這個被劃分為個區域的神地。盧牛告訴了Copy這裡共有個寶藏，分別放在第Pi個(1<=Pi<=N)區域。Copy還得知了每個區域之間的距離。現在Copy從1號區域出發，要獲得所有的寶藏併到n號區域離開。Copy很懶，只好來找你為他尋找一條合適的線路，使得他走過的距離最短。

輸入輸出格式

輸入格式：

第一行一個正整數N(1<=N<=100)

接下來一個N*N的矩陣，第i+1行第j列的數字表示區域i,j之間的距離。每個距離用空格隔開，距離保證i,j<=1000。請註意的i to j距離並不一定等於j to i的距離。

第N+2行一個整數P(0<=P<=10)。

第N+3行共P個用空格隔開的整數，表示有寶藏的區域編號。

輸出格式：

一個整數，為Copy獲得全部寶藏需要的最短距離。數據保證答案小於等於maxlongint。

輸入輸出樣例

樣例輸入1
2
0 4
5 0
2
1 2

樣例輸入2
3
0 2 6
1 0 4
7 10 0
1
2

樣例輸出1
4

樣例輸出1
6

說明

對30%的數據，1<=n<=15，其餘如題所述。

對100%的數據，全部數據範圍如題所述。

 1 #include<bits/stdc++.h> 
 2 #define Max 150
 3 using namespace std;
 4 int a,tx[Max][Max],p,n;
 5 int main()
 6 {
 7     scanf("%d",&n);
 8     for(int i=1;i<=n;++i)
 9         for(int j=1;j<=n;++j)
10            scanf("%d",&tx[i][j]);
11     for(int i=1;i<=n;++i)
12      for(int j=1;j<=n;++j)
13       for(int k=1;k<=n;++k)
14         tx[j][k]=min(tx[j][k],tx[j][i]+tx[i][k]);
15     scanf("%d",&p);
16     int ans=0,minn=0x7fffffff,sx[11];
17     for(int i=1;i<=p;++i) 
18     scanf("%d",&sx[i]);
19     sort(sx+1,sx+1+p);
20     do
21     {
22         ans=0;
23         ans=tx[1][sx[1]]+tx[sx[p]][n];
24         for(int i=1;i<p;++i)
25          ans+=tx[sx[i]][sx[i+1]];//路徑和 
26         minn=min(minn,ans);
27     }while(next_permutation(sx+1,sx+1+p)); 
28     printf("%d\n",minn);
29     return 0;
30 }