P2910 寻宝之路_综合

题目描述

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

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

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

输入输出格式输入格式：第一行：两个用空格隔开的正整数N和M

第二到第M+1行：第i+1行用一个整数Ai表示FJ必须经过的第i个岛屿

第M+2到第N+M+1行：第i+M+1行包含N个用空格隔开的非负整数分别表示i号小岛到第1…N号小岛的航线各自的危险指数。保证第i个数是0。

输出格式第一行：FJ在找到宝藏的前提下经过的航线的危险指数之和的最小值。

说明这组数据中有三个岛屿，藏宝图要求FJ按顺序经过四个岛屿：1号岛屿、2号岛屿、回到1号岛屿、最后到3号岛屿。每条航线的危险指数也给出了：航路(1，2)、(2，3)、(3，1)和它们的反向路径的危险指数分别是5、2、1。

FJ可以通过依次经过1、3、2、3、1、3号岛屿以7的最小总危险指数获得宝藏。这条道路满足了奶牛地图的要求（1，2，1，3）。我们避开了1号和2号岛屿之间的航线，因为它的危险指数太大了。

注意：测试数据中a到b的危险指数不一定等于b到a的危险指数！

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

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

输入输出格式

输入格式：

Line 1: Two space-separated integers: N and M
Lines 2…M+1: Line i+1 describes the i_th island FJ must visit with a single integer: A_i
Lines M+2…N+M+1: Line i+M+1 contains N space-separated integers that are the respective danger rating of the path between island i and islands 1, 2, …, and N, respectively. The ith integer is always zero.

输出格式：

Line 1: The minimum danger that Farmer John can encounter while obtaining the treasure.

输入输出样例

输入样例#1：

输出样例#1：

【解题思路】：

Floyd基础题。

【AC代码】：

#include<bits/stdc++.h>
#define M(a,b) memset(a,b,sizeof(a))
#define pi 3.1415926
using namespace std;
int n,m,ans,i,j,k;
int a[101][101],b[100001];inline void read(int &x){
    char ch=getchar(),c=ch;x=0;while(ch<'0' || ch>'9'){
    c=ch;ch=getchar();}while(ch>='0' && ch<='9'){
    x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}if(c=='-')x=-x;
}int main(){
    read(n),read(m);for(i=1;i<=m;i++)read(b[i]);for(i=1;i<=n;i++)for(j=1;j<=n;j++)read(a[i][j]);for(k=1;k<=n;k++){
        	for(i=1;i<=n;i++){
    for(j=1;j<=n;j++){
    if(i!=j&&j!=k&&k!=i&&a[i][j]>a[i][k]+a[k][j])a[i][j]=a[i][k]+a[k][j];	}}}for(i=2;i<=m;i++)ans+=a[b[i-1]][b[i]];cout<<ans<<'\n';return 0;
}