祝大家2024每场都ak！

朴素的dijkstra 卡着时间(3.7/4)过的晚上补一个堆优化,(不过好像可以用floyd？)

逆天堆优化的dijkstra没过？！

先说思路

考虑情况：
1.可能直接骑车到n点
2.也可能先骑车到其他点再换车再到n点（这其中包括了可能走远路去买一个快车再到n点，也有可能换了很多次车）。
分为这两大类之后我们就可以求出答案了用res来记录每个点到n点的最短时间。
每个res的最小值又有可能是从要求的res的这个点直接到n点和先到其他点m再求从m到n的res
由于我们是用小的res来求出大的res那么我们就要先从车最快的点开始求res

题目描述

斯拉夫的所有朋友都打算骑自行车从他们住的地方去参加一个聚会。除了斯拉维奇，他们都有一辆自行车。他们可以经过 n 个城市。他们都住在城市 1 ，想去参加位于城市 n 的聚会。城市地图可以看作一个无向图，有 n 个节点和 m 条边。边 i 连接城市 ui 和 vi ，长度为 wi 。 斯拉夫没有自行车，但他有的是钱。每个城市都有一辆自行车出售。在 i 这个城市中，自行车的速度系数为 si 。一旦斯拉维奇买了一辆自行车，他就可以在***任何时候用它从他现在所在的城市前往任何邻近的城市，只需花费 wi⋅sj 时间，因为他是在用自己拥有的自行车 j 穿越边缘 i 。 斯拉维奇想买多少辆自行车都可以，因为钱对他来说不是问题。由于斯拉维奇不喜欢骑自行车旅行，他希望在最短的时间内从他的住处到达聚会地点。由于他的信息技能很生疏，他需要你的帮助。 斯拉夫从城市 1 到城市 n 所需的最短时间是多少？斯拉夫没有自行车就无法旅行。保证斯拉夫可以从城市 1 到达其他任何城市。
**输入**
第一行包含一个整数 t ( 1≤t≤100 ) - 测试用例的数量。测试用例说明如下。 每个测试用例的第一行包含两个空格分隔的整数 n 和 m ( 2≤n≤1000 ； n−1≤m≤1000 )--分别是城市数量和道路数量。 下面 m 行的 i (th)分别包含三个整数 ui 、 vi 、 wi ( 1≤ui,vi≤n 、 ui≠vi ； 1≤wi≤105 )，表示城市 ui 和 vi 之间有一条长度为 wi 的道路。同一对城市之间可以有多条道路相连。 下一行包含 n 个整数 s1,…,sn ( 1≤si≤1000 )。( 1≤si≤1000 ) --每辆自行车的速度系数。 所有测试用例的 n 之和不超过 1000 ，所有测试用例的 m 之和不超过 1000 。 输入的附加限制条件：可以从城市 1 出发前往任何其他城市。
**输出**
对于每个测试用例，输出一个整数，表示斯拉夫从城市 1 出发到达城市 n 所需的最短时间。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
typedef long long LL;

typedef pair<LL,LL> PII;
LL w[N][N];
LL res[N];
PII s[N];
void dijkstra(LL x,LL v,int n)//最短路算法都可以
{
    LL d[N];
    memset(d,0x3f,sizeof d);
    bool st[N] = {0};
    d[x] = 0;
    for(int i = 0;i<n-1;i++)
    {
        int t = -1;
        for(int j = 1;j<=n;j++)
            if(!st[j]&&(t == -1||d[t]>d[j]))
                t = j;
        st[t] = true;
        for(int j = 1;j<=n;j++)
            d[j] = min(d[j],d[t]+w[t][j]);

    }
    res[x] = v*d[n];
    for(int i = 1;i<=n;i++)
        if(res[i] != -1)
        res[x] = min(res[x],v*d[i]+res[i]);
}
void solve()
{
    int n,m;
    scanf("%d%d",&n,&m);
    memset(w,0x3f,sizeof w);
    memset(res,-1,sizeof res);
    for(int i = 0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        w[a][b] = min(w[a][b],(LL)c);
        w[b][a] = w[a][b];
    }
    for(int i = 1;i<=n;i++) 
    {
        scanf("%d",&s[i].first);
        s[i].second = i;
    }
    sort(s,s+n);
    for(int i = 1;i<=n;i++)//这里换成floyd看看
    {
        dijkstra(s[i].second,s[i].first,n);
    }
    cout<<res[1]<<endl;
}
int main()
{
    int n;
    cin >> n;
    while (n -- ){
        solve();
    }
    return 0;
}