洛谷P2009 跑步

url: https://www.luogu.com.cn/problem/P2009

tag:
图论，最短路

思路：
这道题因为读入的时候，会有不同权值的相同的边，要求是如果有重复的就保留最长的那个，这种情况下用邻接链表不是很好做，所以可以用邻接矩阵来存比较方便。然后就是数据范围比较小，k是小于等于100，刚好floyd算法可以过，所以就用floyd来求最短路。

代码：

#include <iostream>
#include <cstring>
using namespace std;
int main()
{
    int d[110][110];
    memset(d, 0x3f, sizeof d);
    int n, k;
    cin >> n >> k ;
    int c = 0;
    for (int i = 0; i < n; i ++)
    {
        int w;
        cin >> w;
        if (i == n - 1)
        {
            d[i][0] = d[0][i] = w;
        }
        else
        {
            d[i][i + 1] = d[i + 1][i] = w;
        }
    }
    for (int i = 0; i < k; i ++)
    {
        char a, b;
        int w;
        cin >> a >> b >> w;
        if (d[a - 'A'][b - 'A'] == 0x3f3f3f3f) d[a - 'A'][b - 'A'] = d[b - 'A'][a - 'A'] = w;
        else d[a - 'A'][b - 'A'] = d[b - 'A'][a - 'A'] = max(w, d[a - 'A'][b - 'A']);
    }
    for (int q = 0; q < n; q ++)
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < n; j ++)
                d[i][j] = min(d[i][j], d[i][q] + d[q][j]);
    char s, t;
    cin >> s >> t;
    cout << d[s - 'A'][t - 'A'];
    return 0;
}