首页 > 代码库 > BZOJ 1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路
BZOJ 1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路
Description
农夫约翰正驾驶一条小艇在牛勒比海上航行．
海上有N(1≤N≤100)个岛屿，用1到N编号．约翰从1号小岛出发，最后到达N号小岛．一
张藏宝图上说，如果他的路程上经过的小岛依次出现了Ai，A2，…，AM(2≤M≤10000)这样的序列（不一定相邻），那他最终就能找到古老的宝藏． 但是，由于牛勒比海有海盗出没．约翰知道任意两个岛屿之间的航线上海盗出没的概率，他用一个危险指数Dij(0≤Dij≤100000)来描述．他希望他的寻宝活动经过的航线危险指数之和最小．那么，在找到宝藏的前提下，这个最小的危险指数是多少呢？
Input
第1行输入N和M，之后M行一行一个整数表示A序列，之后输入一个NxN的方阵，表示两两岛屿之间航线的危险指数．数据保证Dij=Dji，Dii=0．
Output
最小的危险指数和．
题解：
因为要依次出现，从Ai到Ai+1,其中走的一定是它俩之间的最短路，所以可以对整个图Floyd。然后将两两之间最短路加起来就是答案。
代码：
#include<cstdio>#include<cstring>#include<algorithm>//by zrt//problem:using namespace std;int n;int dis[105][105]; int m,a[10005];int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d",&a[i]); } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%d",&dis[i][j]); } } for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } } } long long ans=0; for(int i=2;i<=m;i++){ ans+=dis[a[i-1]][a[i]]; } printf("%lld\n",ans); return 0;}
BZOJ 1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。