P2910 [USACO08OPEN]Clear And Present Danger S题解

bfac3402-1150-46c7-8798-f545389dbac3
其使用最简单的方法做就好了忘了啥名字，类似于dp
给个代码

#include<bits/stdc++.h>

using namespace std;

long long n,m;

long long c[105][105];

long long ans;

short l[100000];

int main() {

	cin >> n >> m;

	for (int i = 1; i <= m; i++) cin >> l[i];

	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= n; j++) {

			cin >> c[i][j];

		}

	}

	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= n; j++) {

			for (int k = 1; k <= n; k++) {

				c[j][k] = min(c[j][k],c[j][i] + c[i][k]);

			}

		}

	}

	for(int i = 2; i <= m; i++) {

		ans += c[l[i - 1]][l[i]];

	}

	cout << ans << endl;

	return 0;

}

/*

3 4

1

2

1

3

0 5 1

5 0 2

1 2 0 

7

*/

注意：是for这样的

~~~~~~~~~~~~~

【重要】

------中转点
----------第一个点
--------------第二个点
再给个模板

for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= n; j++) {

			for (int k = 1; k <= n; k++) {

				c[j][k] = min(c[j][k],c[j][i] + c[i][k]);

			}

		}

	}

巴特西

P2910 [USACO08OPEN]Clear And Present Danger S题解

最新文章

热门文章