传送门:牛客

题目描述

农夫约翰正驾驶一条小艇在牛勒比海上航行．
海上有 $N(1\le N\le 100)$ 个岛屿，用 $1$ 到 $N$ 编号．约翰从 $1$ 号小岛出发，最后到达 $N$ 号小岛．
一张藏宝图上说，如果他的路程上经过的小岛依次出现了 $A_1,A_2,\dots ,A_M(2\le M\le 10000)$ 这样的序列（不一定相邻），那他最终就能找到古老的宝藏． 但是，由于牛勒比海有海盗出没．约翰知道任意两个岛屿之间的航线上海盗出没的概率，他用一个危险指数 $D_{i,j}(0\le D_{i,j}\le 100000)$ 来描述．他希望他的寻宝活动经过的航线危险指数之和最小．那么，在找到宝藏的前提下，这个最小的危险指数是多少呢？

输入:
3 4 
1 
2 
1 
3 
0 5 1 
5 0 2 
1 2 0 
输出:
7

一道简单的多源最短路的题目.N并不是很大,所以使用$Floyd$来解决这道题

对于$floyd$网上有大量的博客和题解,不乏讲的很清楚的(肯定比我讲的要清楚),所以此处就不再赘述了

提醒一下:学完之后可以考虑一下为什么$floyd$的中间点循环需要放在最外面而不能是最里面,这可以增加对$floyd$算法的理解!

下面是具体的代码部分:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n,m;
int dis[200][200];int edge[maxn];
int main() {
	n=read();m=read();
	for(int i=1;i<=m;i++) edge[i]=read();
	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]);
			}
		}
	}
	int ans=0;
	if(edge[1]!=1) ans+=dis[1][edge[1]];
	for(int i=2;i<=m;i++) {
		ans+=dis[edge[i-1]][edge[i]];
	}
	if(edge[m]!=n) ans+=dis[edge[m]][n];
	cout<<ans<<endl;
	return 0;
}