bzoj1624 寻宝之路
2024-09-06 11:34:25
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
最小的危险指数和.
Sample Input
3 4
1
2
1
3
0 5 1
5 0 2
1 2 0
1
2
1
3
0 5 1
5 0 2
1 2 0
INPUT DETAILS:
There are 3 islands and the treasure map requires Farmer John tovisit a sequence of 4 islands in order: island 1, island 2, island1 again, and finally island 3. The danger ratings of the paths aregiven: the paths (1, 2); (2, 3); (3, 1) and the reverse paths havedanger ratings of 5, 2, and 1, respectively.
Sample Output
7
OUTPUT DETAILS:
He can get the treasure with a total danger of 7 by traveling inthe sequence of islands 1, 3, 2, 3, 1, and 3. The cow map's requirement(1, 2, 1, and 3) is satisfied by this route. We avoid the pathbetween islands 1 and 2 because it has a large danger rating.
看到是floyd感觉好久没有写过了就水一发。
结果maxm写成maxn。智障错误第二次:手打堆
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=100+10,maxm=1e4+10;
int n,m,a[maxm];//
long long dis[maxn][maxn],ans; long long aa;char cc;
long long read() {
aa=0;cc=getchar();
while(cc<'0'||cc>'9') cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
return aa;
} int main() {
n=read();m=read();a[0]=1;
for(int i=1;i<=m;++i) a[i]=read();a[m+1]=n;
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) dis[i][j]=read();
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]);
for(int i=0;i<=m;++i) ans+=dis[a[i]][a[i+1]];
cout<<ans;
return 0;
}
最新文章
- 破除Odoo 菜单栏提示 99+
- 使用CSS3 制作一个material-design 风格登录界面
- 转载:C#保存文件时重名自动生成新文件的方法
- Oracle创建用户、表空间并设置权限
- Bug避障算法简介
- weblogic解密工具
- 菜鸟学sql,Oracle数据库结构比较
- fzu 1913 Easy Comparison(字符串)
- 译-HTTP-GET HTTP-POST SOAP protocol for ASP.NET services的异同
- Node与apidoc的邂逅——NodeJS Restful 的API文档生成
- 使用python UIAutomation从QQ2017(v8.9)群界面获取所有群成员详细资料,
- UOJ#424. 【集训队作业2018】count 多项式,FFT,矩阵
- 东软实习<;2>;
- 一种hyperscan API使用(1)
- Intellij IDEA 设置启动JVM参数
- Solidity的三种转账方式与比较
- JAVA实现具有迭代器的线性表(顺序表)
- MarkDown,写出个性、漂亮的文档
- oracle的中文排序问题
- 【Unity】2.5 场景视图(Scene)
热门文章
- PAT甲级——A1025 PAT Ranking
- spring boot 源码解析11-ConfigurationClassPostProcessor类加载解析
- 901. Online Stock Span [短于线性的时间统计单个元素的Span ]
- mysql建表设置格式
- Hadoop Serialization hadoop序列化详解(最新版) (1)【java和hadoop序列化比较和writable接口】
- apk反编译(6)用ProGuard 混淆、压缩代码,压缩资源。
- H5C3--属性选择器、兄弟选择器、伪类选择器
- Delphi 设计模式:《HeadFirst设计模式》Delphi7代码---适配器模式之TurkeyAdapter[转]
- tomcat9下载与安装
- MaxCompute Spark开发指南