题解 P2009 【跑步】
ShineEternal
2019-10-24 22:18:15
[$My\ blog$](https://blog.csdn.net/kkkksc03/article/details/102733586)
看到题解少，来补充一篇。。。
## description（notes）：
变相给出一个图求最短路，对特殊情况有特殊要求
## solution：
这道题观察到数据范围小的可怜，便可以使用Floyd算法解决。
在刚刚处理的时候，要注意一句话
> 如果两点之间有多条道路直接连接，他会选择最长的那条。
所以如果这一条边中已经记录了数据，就取个max就行了。
对于多边形的边上和里面的连线都做这样的操作。
然后跑Floyd
**注意：**
- scanf和cin最好不要一块用。
- 最短路别忘了赋初值
- 字符转为数字下标考虑清楚是从0还是1开始
## code:
```cpp
#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;
}
```