題目描述

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：
樣例輸入1 2 0 4 5 0 2 1 2樣例輸入2 3 0 2 6 1 0 4 7 10 0 1 2 輸出樣例#1：
樣例輸出1 4樣例輸出1 6

說明

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

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

?

floyd+全排列?

屠龍寶刀點擊就送

#include <algorithm> #include <cstring> #include <cstdio> #define Max 150 using namespace std;int a,tx[Max][Max],p,n; void floyd() {for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)for(int k=1;k<=n;++k)tx[j][k]=min(tx[j][k],tx[j][i]+tx[i][k]);scanf("%d",&p);int ans=0,Answer=0x7fffffff,sx[11];for(int i=1;i<=p;++i) scanf("%d",&sx[i]);sort(sx+1,sx+1+p);do{ans=0;ans=tx[1][sx[1]]+tx[sx[p]][n];for(int i=1;i<p;++i) ans+=tx[sx[i]][sx[i+1]];Answer=min(Answer,ans);}while(next_permutation(sx+1,sx+1+p)); printf("%d",Answer); } int main() {scanf("%d",&n);for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)scanf("%d",&tx[i][j]);floyd();return 0; }

?

轉載于:https://www.cnblogs.com/ruojisun/p/6580425.html

總結

以上是生活随笔為你收集整理的洛谷 P1690 贪婪的Copy的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。