本文主要是介绍1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
floyd跑出最短路后按a顺序相加即可
#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i =x ;i <= y; ++ i)
#define repd(i,x,y) for(register int i = x; i >= y ; -- i)
using namespace std;
template<typename T>inline void read(T&x)
{x = 0;char c;int sign = 1;do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));x *= sign;
}const int N = 101;
int a[10100],d[N][N],n,m;int main()
{read(n);read(m);rep(i,1,m) read(a[i]);rep(i,1,n)rep(j,1,n)read(d[i][j]);rep(k,1,n)rep(i,1,n)rep(j,1,n)d[i][j] = min(d[i][k] + d[k][j],d[i][j]);int s = 1,ans = 0;rep(i,1,m){ans += d[s][a[i]];s = a[i];} cout << ans << endl;return 0;
}
这篇关于1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!