题目描述

在古老的历史之中，有一个神秘的传说，那就是炼金术，这是一种可以转化为贵重金属的神秘法术。尽管大多数人都认为这只是个传说，但仍然有一些人相信它的存在，包括珠宝商，小度。

小度是一个对炼金术有着无尽痴迷的商人。他拥有两串各自由$n$个稀有金属珠子构成的项链，每一串项链都价值连城，然而，项链的价值并不仅仅在于它们的稀有，如果两串项链变得一摸一样将会具有对称的美丽。但受限于稀有金属的稀缺性，小度始终无法凑出足够的稀有金属获得两串一样的项链，小度始终有一个想法：如果炼金术是真的，他是否能够通过炼金术的转化，让这两串项链变得更完美，拥有对称之美呢？

于是，小度开始翻阅古书，进行了他的炼金术实验。他将自己关在工作室中，日夜不停地研究，试图找到将这对项链转化为一样的方法。然而，炼金术并非易事，他失败了无数次，但小度并没有放弃，他在古书和实验的帮助下发现了$m$条可以复现实验的炼金术，一项炼金术可以花费$c_i$小时将稀有金属$a_i$变成稀有金属$b_i$ 。

然而小度的工作室条件有限，只能够同时进行一项炼金术，小度为了尽早达成夙愿他会夜以继日，他会采取最优的方法将两条项链通过炼金术获得两串一样的项链，只是项链是一个环，他不知道从哪一个位置开始会花费最小的天数，退而求其次，小度想知道他随机选择两个项链上的一个珠子开始逐一往后通过最优的策略使用炼金术的话，达成夙愿的期望小时数会是多少？

输入格式：

第$1$行输入两个数$n$ $m$ $(1 \le n \le 10^5 , 1 \le m \le 10^6)$
接下来 $1$ 行，$n$个数$s_1 , s_2 , ··· , s_n $ 表示第一条项链从左到右稀有金属的种类；
接下来 $1$ 行，$n$个数$t_1 , t_2 , ··· , t_n $ 表示第二条项链从左到右稀有金属的种类；
接下来$m$行，每行三个数 $a_i b_i c_i$ ，含义与题目描述一致，$ (1 \le s_i , t_i , a_i , b_i \le 400 , 1 \le c_i \le 100) $
可能存在多个将 $a_i$ 变为 $b_i$ 的炼金术，保证所有金属可以互相转换。

输出格式：

一行，一个保留$2$位小数的浮点数，表示期望的小时数。

样例输入：

3 14
4 5 3 
2 4 3 
3 2 65
2 3 38
4 2 55
2 4 95
4 3 88
3 4 58
5 2 84
2 5 24
5 3 23
3 5 97
5 4 25
4 5 23
4 5 33
1 2 100

样例输出：

82.33

题目分析

刚开始以为很简单，直接就写了，然后就TLE了
看题目很容易看出这道题考的是多源汇最短路，直接就用Floyd做，

Floyd时间复杂度$O({cnt}^3)$ 约等于 $7 * 10^7$

本以为是能过的，结果后来发现要$n^2$ 然后就挂了

C++ 代码1：

未优化
7 / 11 TLE 做法 时间复杂度$O(n^2 * cnt)$

#include<bits/stdc++.h> 

using namespace std;
const int N = 100010 , M = 410;
int dist[M][M];
int s[N] , t[N];
int n , m;
int cnt = 0;
void floyd()
{
    for (int k = 1; k <= cnt; k ++ )
        for (int i = 1; i <= cnt; i ++ )
            for (int j = 1; j <= cnt; j ++ )
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

int main( )
{
    cin >> n >> m;
    for(int i = 0 ; i < n ; i ++) cin >> s[i];
    for(int i = 0 ; i < n ; i ++) cin >> t[i];

    for(int i = 1 ; i < M  ; i ++)
        for(int j = 1 ; j < M  ; j ++)
            if(i == j) dist[i][j] = 0;
            else dist[i][j] = 0x3f3f3f3f;

    while(m --)
    {
        int a , b , c;
        cin >> a >> b >> c;
        dist[a][b] = min(dist[a][b] , c);
        cnt = max(cnt , max(b , a));
    }
    floyd();

    long long res = 0ll;
    for(int i = 0 ; i < n ; i ++)
    {
        long long now = 0;
        for(int j = 0 ; j < n ; j ++)
        {
            int sc = s[j] , tc = t[(i + j) % n];
            int cost = 0x3f3f3f3f;
            for(int k = 1 ; k <= cnt ; k ++)
                cost = min(cost , dist[sc][k] + dist[tc][k]);
            res += cost;
        }
    }
    long double ans = 1. * res / n;
    printf("%.2Lf" , ans);
    return 0;
}

接下来就是优化了
其实就是把$n$缩小，看数据可以知道其实$s$、$t$中大部分都是重复字符，所以用map来优化
而且在每次循环中可以发现

for(int k = 1 ; k <= cnt ; k ++)
    cost = min(cost , dist[sc][k] + dist[tc][k]);

这个操作其实可以预处理，用单独的数组存一下任意两个字符选择变成那个字符最优即可

C++代码 时间复杂度$O(max${$ {log^2(n)} , cnt^3 $}$)$

#include<bits/stdc++.h> 

using namespace std;
const int N = 100010 , M = 410;
int dist[M][M];
int g[M][M];
int s[N] , t[N];
map<int , int> q1 , q2;
int n , m;
int cnt = 0;
void floyd()
{
    for (int k = 1; k <= cnt; k ++ )
        for (int i = 1; i <= cnt; i ++ )
            for (int j = 1; j <= cnt; j ++ )
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

void cal()
{
    for (int k = 1; k <= cnt; k ++ )
        for (int i = 1; i <= cnt; i ++ )
            for (int j = 1; j <= cnt; j ++ )
                if(i == j) g[i][j] = 0;
                else g[i][j] = min(g[i][j] , dist[i][k] + dist[j][k]);
}

int main( )
{
    cin >> n >> m;
    for(int i = 0 ; i < n ; i ++)
    {
        cin >> s[i];
        q1[s[i]] ++;
    } 
    for(int i = 0 ; i < n ; i ++)
    {
        cin >> t[i];
        q2[t[i]] ++;
    } 

    for(int i = 1 ; i < M  ; i ++)
        for(int j = 1 ; j < M  ; j ++)
            if(i == j) dist[i][j] = 0;
            else dist[i][j] = 0x3f3f3f3f;

    while(m --)
    {
        int a , b , c;
        cin >> a >> b >> c;
        dist[a][b] = min(dist[a][b] , c);
        cnt = max(cnt , max(b , a));
    }
    floyd();
    memset(g , 0x3f , sizeof g);
    cal();
    long long res = 0ll;
    for(auto [k1 , v1] : q1)
        for(auto [k2 , v2] : q2)
            res += (long long) v1 * v2 * g[k1][k2];
    long double ans = 1. * res / n;
    printf("%.2Lf" , ans);
    return 0;
}