M y <mtext>   </mtext> b l o g My\ blog My blog

看到题解少，来补充一篇。。。

description（notes）：

变相给出一个图求最短路，对特殊情况有特殊要求

solution：

这道题观察到数据范围小的可怜，便可以使用Floyd算法解决。

在刚刚处理的时候，要注意一句话

如果两点之间有多条道路直接连接，他会选择最长的那条。

所以如果这一条边中已经记录了数据，就取个max就行了。

对于多边形的边上和里面的连线都做这样的操作。

然后跑Floyd

注意：

  • scanf和cin最好不要一块用。

  • 最短路别忘了赋初值

  • 字符转为数字下标考虑清楚是从0还是1开始

code:

#include<cstdio>
#include<iostream>
#define inf 0x3f3f3f3f
using namespace std;
int a[105][105];
int main()
{
	int n,k,x;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			a[i][j]=inf;
		}
	}
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		if(a[i][i%n+1]!=inf)
		{
			a[i][i%n+1]=a[i%n+1][i]=max(x,a[i%n+1][i]);
		}
		else
		{
			a[i][i%n+1]=a[i%n+1][i]=x;
		}
	}
	char s,e;
	for(int i=1;i<=k;i++)
	{
		int val;
		cin>>s>>e>>val;
		
		int x=s-'A'+1;
		int y=e-'A'+1;
		if(a[x][y]!=inf)
		{
			a[x][y]=a[y][x]=max(val,a[x][y]);
		}
		else
		{
			a[x][y]=a[y][x]=val;
		}
	}
	char n1,n2;
	cin>>n1>>n2;
	int ans1=n1-'A'+1;
	int ans2=n2-'A'+1;
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
			}
		}
	} 
	cout<<a[ans1][ans2]<<endl;
	return 0;
}