题解 P2910 【[USACO08OPEN]寻宝之路Clear And Present Danger】

天下至菜 · 2019-10-22 21:11:18 · 题解

显然是一道最短路题

题意大概就是按照他给的顺序走一遍就可以了？

先处理好所有点之间的距离就好了

#include<bits/stdc++.h>
#define ll long long
#define F(i,j,k) for(ll i=j;i<=k;i++)//缩写for循环
#define F2(i,j,k) for(ll i=j;i>=k;i--)
using namespace std;
ll read(){//快读
    ll f=1,sum=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();}
    return f*sum;
}
ll n,m,f[105][105],to[10005],ans;
int main(){
    n=read();m=read();
    F(i,1,m)to[i]=read();
    F(i,1,n)F(j,1,n)f[i][j]=read();
    F(k,1,n)F(i,1,n)F(j,1,n)f[i][j]=min(f[i][j],f[i][k]+f[k][j]);//处理各个点之间的距离
    F(i,1,m-1){ans+=f[to[i]][to[i+1]];}//注意，一定要加到m-1
    printf("%lld",ans);
    return 0;
}