JDOJ2585 Clear And Present Danger


题目大意

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

海上有N(1≤N≤100)个岛屿,用1到N编号.约翰从1号小岛出发,最后到达N号小岛.

一张藏宝图上说,如果他的路程上经过的小岛依次出现了Ai,A2,…,AM(2≤M≤10000)这样的序列(不一定相邻),那他最终就能找到古老的宝藏. 但是,由于牛勒比海有海盗出没.约翰知道任意两个岛屿之间的航线上海盗出没的概率,他用一个危险指数Dij(0≤Dij≤100000)来描述.他希望他的寻宝活动经过的航线危险指数之和最小.那么,在找到宝藏的前提下,这个最小的危险指数是多少呢?

 

这道题看起来很恶心……实际上很简单OvO只是按一定顺序的话看到数据范围直接Floyd然后求一下不久可以了嘛OvO

#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int n,m,ord[10010],dis[110][110];
long long ans;
 
void floyd()
{
    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]);
    return;
}
 
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i) scanf("%d",&ord[i]);
    ord[0]=1;
    ord[++m]=n;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j) scanf("%d",&dis[i][j]);
    floyd();
    for(int i=1;i<=m;++i)
        ans+=dis[ord[i-1]][ord[i]];
    printf("%lld",ans);
    return 0;
}

 

声明:TonyZhao's Home|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - JDOJ2585 Clear And Present Danger


不骗了,不骗了。
A Simple OIer fighting tooth and nail.