最短路径Floyd算法

第一题：[USACO08OPEN] Clear And Present Danger S

#include<bits/stdc++.h>
using namespace std;
int n,m;
int g[105][105];
int arr[100005];
long long sum;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&arr[i]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&g[i][j]);
		}
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(g[i][j]>g[i][k]+g[k][j])
				{
					g[i][j]=g[i][k]+g[k][j];
				}
			}
		}
	}
	int a=1,b=0;
	for(int i=1;i<=m;i++)
	{
		b=arr[i];
		sum+=g[a][b];
		a=b;
	}
	printf("%lld",sum);
	return 0;
}

第二题：传送闭包 

#include<bits/stdc++.h>
using namespace std;
int n;
int g[105][105];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&g[i][j]);
		}
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				g[i][j]=max(g[i][j],g[i][k]&g[k][j]);
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			printf("%d ",g[i][j]);
		}
		printf("\n");
	}
	return 0;
 } 

第三题：传送门 

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[105][105];
void floyd()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			{
				if(a[j][k]>a[j][i]+a[i][k])
				a[j][k]=a[j][i]+a[i][k];
			}
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i==j)
			a[i][j]=0;
			else
			a[i][j]=0x3f3f3f3f;
		}
	}
	int x,y,z;
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		a[x][y]=a[y][x]=z;
	}
	floyd();
	long long sum=0x3f3f3f3f;
	for(int i=1;i<=n;i++)
	{
		for(int j=1+i;j<=n;j++)
		{
			long long sum2=0;
			for(int p=1;p<=n;p++)
			{
				for(int q=1+p;q<=n;q++)
				{
					sum2+=min(a[p][q],min(a[p][i]+a[j][q],a[p][j]+a[i][q]));
				}
			}
			sum=min(sum,sum2);
		}
	}
	printf("%lld",sum);
	return 0;
}