Floyd

租用游艇

题目：P1359 租用游艇 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题解：     1.首先明确这是一个简单的有向图求最短路的问题，对于新手来说，Floyd算法入门题。

                2.一个地图数组，存储两个出租点的权重，初始化地图数组，除了到达本身，map数组的值为0，其实全部设置成无穷大（即比最大的权重还要大的数）。

                 3.Floyd算法，三个for循环迭代，将map数组更新。三层for循环中第一层是一个中间值v（i！=j！=v），判断一下map[i][j]是否大于r[i][v]+r[v][j]，确认v是否为中转点。

                4.最后的结果就是map[1][n];

代码如下

#include
using namespace std;
int r[201][201];//r数组的大小是由出租点的数量决定的
#define max 1e6;
int main()
{
	int n;
	cin>>n;
	int i,j,v;
	for(i=1;i>r[i][j];
	}
	for(v=1;v<=n;v++)
	for(i=1;ir[i][v]+r[v][j])
		{
			r[i][j]=r[i][v]+r[v][j];
		}
	}
	cout< 
[USACO08OPEN]Clear And Present Danger S
 
题目：P2910 [USACO08OPEN]Clear And Present Danger S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 
题解：    1.首先明确这是一个简单的有向图求最短路的问题，由于数据不太复杂，所以可以用Floyd算法。
 
                2.和上面一题的解法差不多，这里要添加一个数组记录一下顺序岛屿的顺序。最后输出的时候，遍历相加一下，结果就出来了。
 
                3.和上一题写法不同的是r[i][j]=min(r[i][v]+r[v][j],r[i][j]);这里简化了一下。
 
代码如下
 
#include
using namespace std;
int main()
{
	int n,m;
	int r[101][101],t[10009];
	cin>>n>>m;
	int i,j,v;
	for(i=1;i<=m;i++)
	cin>>t[i];
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	{
		cin>>r[i][j];
	}
	for(v=1;v<=n;v++)
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++) 
	{
		r[i][j]=min(r[i][v]+r[v][j],r[i][j]);
	}
	int ans=0;
	for(i=2;i<=m;i++)
	ans+=r[t[i-1]][t[i]];
	cout<