tyvj 1288

飘飘乎居士取能量块~~

是个最短路+哈密顿路径问题。

所以floyd+next_permutation

这个题确实给全排列的算法提了个醒

全排列最好用do whille 写，为什么呢？【【你去问哀家】】

哈哈 是因为，while 会把第一个牲畜排列跳过去。所以你的答案当然就不一定准确了。不一定？是因为这题数据特别水、、

#include
#include
#include
#include
#define inf 999999
using namespace std;
//by mars_ch
int n;
int map[101][101];
int dp[101][101];
int p;
int pos[11];
int vis[101];
void floyd()
{for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){map[i][j]=min(map[i][j],map[i][k]+map[k][j]);}}}
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&map[i][j]);}}scanf("%d",&p);for(int i=1;i<=p;i++){scanf("%d",&pos[i]);}floyd();pos[0]=1;  //没有能量块也要从1开始哦 int mina=999999,sum;sort(pos+1,pos+p+1);       //   next_permutation这个东西比较神奇。最好排序一遍 for(int i=1;i<=p;i++){sum+=map[pos[i-1]][pos[i]];}sum+=map[pos[p]][n];mina=min(sum,mina);    //为什么要预处理？想题目给的良心数据就是没法全排列的。 do{/*for(int i=1;i<=p;i++){printf("%d ",pos[i]);}printf("\n");*/sum=0;for(int i=1;i<=p;i++){sum+=map[pos[i-1]][pos[i]];}sum+=map[pos[p]][n];mina=min(mina,sum);}while(next_permutation(pos+1,pos+p+1));printf("%d\n",mina);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！