【BZOJ】1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路(floyd)
and open BZOJ Floyd Clear present
2023-09-27 14:22:21 时间
http://www.lydsy.com/JudgeOnline/problem.php?id=1624
一开始我打算一个个最短路。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
然后没想到。。。。。floyd。。。
吐血。。
很简单,裸floyd即可。
#include <cstdio> #include <cstring> #include <cmath> #include <string> #include <iostream> #include <algorithm> #include <queue> using namespace std; #define rep(i, n) for(int i=0; i<(n); ++i) #define for1(i,a,n) for(int i=(a);i<=(n);++i) #define for2(i,a,n) for(int i=(a);i<(n);++i) #define for3(i,a,n) for(int i=(a);i>=(n);--i) #define for4(i,a,n) for(int i=(a);i>(n);--i) #define CC(i,a) memset(i,a,sizeof(i)) #define read(a) a=getint() #define print(a) printf("%d", a) #define dbg(x) cout << #x << " = " << x << endl #define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; } inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; } inline const int max(const int &a, const int &b) { return a>b?a:b; } inline const int min(const int &a, const int &b) { return a<b?a:b; } const int N=105; int f[N][N], n, m, a[10005]; long long ans; int main() { read(n); read(m); for1(i, 1, m) read(a[i]); for1(i, 1, n) for1(j, 1, n) read(f[i][j]); for1(k, 1, n) for1(i, 1, n) for1(j, 1, n) f[i][j]=min(f[i][j], f[i][k]+f[k][j]); for1(i, 2, m) ans+=f[a[i-1]][a[i]]; ans+=f[1][a[1]]; ans+=f[a[m]][n]; printf("%lld", ans); return 0; }
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
INPUT DETAILS:
There are 3 islands and the treasure map requires Farmer John to
visit a sequence of 4 islands in order: island 1, island 2, island
1 again, and finally island 3. The danger ratings of the paths are
given: the paths (1, 2); (2, 3); (3, 1) and the reverse paths have
danger ratings of 5, 2, and 1, respectively.
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 to
visit a sequence of 4 islands in order: island 1, island 2, island
1 again, and finally island 3. The danger ratings of the paths are
given: the paths (1, 2); (2, 3); (3, 1) and the reverse paths have
danger 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 in
the 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 path
between islands 1 and 2 because it has a large danger rating.
OUTPUT DETAILS:
He can get the treasure with a total danger of 7 by traveling in
the 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 path
between islands 1 and 2 because it has a large danger rating.
HINT
Source
相关文章
- Leetcode: Ones and Zeroes
- Leetcode: Best Time to Buy and Sell Stock
- 解决MySQL报错:1 of ORDER BY clause is not in GROUP BY clause and contains nonaggregated column 'informat
- ConcurrentBag of strings and using .Contains in Parallel.ForEach
- Host key for * has changed and you have requested strict checking.Host key verification failed.
- 【CF679D】Bear and Chase 最短路+乱搞
- 2015 Multi-University Training Contest 10 hdu 5407 CRB and Candies
- Open source and free log analysis and log management tools.
- CodeForces 719B Anatoly and Cockroaches (水题贪心)
- Look Further to Recognize Better: Learning Shared Topics and Category-Specific Dictionaries for Open-Ended 3D Object Recognition
- swift语言点评六-Numbers and Basic Values
- <Multi-View Image Classification With Visual, Semantic and View Consistency>笔记
- Vite 使用记录:动态导入静态图片、vite项目报错Only file and data URLs are supported by the default ESM loader解决、Vite多环境配置
- 【DeepLearning】Exercise:Convolution and Pooling
- jenkins with gitblit and .net framework and windows