bzoj1624

分析：我真是做题做傻了。。居然在想什么奇怪的dp。。直接floyd之后随便算不好吗？？？我居然老是想O(MN)的dp，看来不能被数据范围所左右。。

#include<cstdio> #include<algorithm> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; int n,m; const int N=1e5+5; const int M=1e3+5; int a[N]; int f[M][M]; int main() { scanf("%d%d",&n,&m); fo(i,1,m)scanf("%d",&a[i]); fo(i,1,n) fo(j,1,n)scanf("%d",&f[i][j]); fo(k,1,n) fo(i,1,n) fo(j,1,n) if(i!=j&&j!=k&&k!=i) { f[i][j]=min(f[i][k]+f[k][j],f[i][j]); } a[0]=1; int ans=0; fo(i,1,m) { ans+=f[a[i-1]][a[i]]; } printf("%d\n",ans); }