BZOJ 1624 [Usaco2008 Open] Clear And Present Danger 寻宝之路：floyd

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1624

题意：

　　农夫约翰正驾驶一条小艇在牛勒比海上航行。

　　海上有N(1≤N≤100)个岛屿，用1到N编号。

　　约翰从1号小岛出发，最后到达N号小岛。

　　一张藏宝图上说，如果他的路程上经过的小岛依次出现了Ai，A2，…，AM(2≤M≤10000)这样的序列（不一定相邻），那他最终就能找到古老的宝藏。

　　但是，由于牛勒比海有海盗出没．约翰知道任意两个岛屿之间的航线上海盗出没的概率，他用一个危险指数Dij(0≤Dij≤100000)来描述。

　　他希望他的寻宝活动经过的航线危险指数之和最小。

　　那么，在找到宝藏的前提下，这个最小的危险指数是多少呢？

题解：

　　floyd.

　　然后求从1到a[1]、a[1]到a[2]...a[m]到n的dis之和。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAX_N 105

 #define MAX_M 10005

 using namespace std;

 int n,m;

 int ans=;

 int a[MAX_M];

 int dis[MAX_N][MAX_N];

 void read()

 {

     cin>>n>>m;

     a[]=;

     a[m+]=n;

     for(int i=;i<=m;i++)

     {

         cin>>a[i];

     }

     for(int i=;i<=n;i++)

     {

         for(int j=;j<=n;j++)

         {

             cin>>dis[i][j];

         }

     }

 }

 void floyd()

 {

     for(int k=;k<=n;k++)

     {

         for(int i=;i<=n;i++)

         {

             for(int j=;j<=n;j++)

             {

                 if(i!=j && j!=k && i!=k)

                 {

                     dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

                 }

             }

         }

     }

 }

 void solve()

 {

     floyd();

     for(int i=;i<=m;i++)

     {

         ans+=dis[a[i]][a[i+]];

     }

 }

 void print()

 {

     cout<<ans<<endl;

 }

 int main()

 {

     read();

     solve();

     print();

 }

巴特西

BZOJ 1624 [Usaco2008 Open] Clear And Present Danger 寻宝之路：floyd

最新文章

热门文章