ShineEternal的小书屋

ShineEternal的小书屋

https://blog.csdn.net/kkkksc03

题解 P2009 【跑步】

posted on 2019-10-24 22:18:15 | under 题解 |

$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;
}