F.
找了些题解，但都看的不是很懂
先去又梳理了一遍堆优化版的dij
每次用当前可到达的最小的边去进行松弛操作
标记数组，若该点已经加入确定点集，就跳过
别忘了dist[]数组初始化为无穷大，这样才会全部都被更新
#define ll long long
const int inf=0x3f3f3f3f;
const int N=1e5+10;
int n,m,s;//s是起点
vector<pair<int,int>> g[N];
int dist[N];
bool st[N];//是否加入确定的点集
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
void dij(){
memset(dist,inf,sizeof(dist));//初始化
dist[s]=0;
q.push({0,s});
while(q.size()){
auto k=q.top();q.pop();
int ver=k.second,distance=k.first;
if(st[ver])continue;
st[ver]=true;
for(int i=0;i<g[ver].size();i++){
int j=g[ver][i].first;
if(dist[j]>distance+g[ver][i].second){
dist[j]=distance+g[ver][i].second;
q.push({dist[j],j});
}
}
}
}
然后果真思路清晰了起来+一些题解的支点
但挣扎一番后，困在了定性思维
dist[][]的二维数组，第一维是点，第二维是速率
因为数据都不大，这样做没问题
我默认速率是这个点要确定的速率，因此没法儿做，要么枚举不了那么多状态，要么没办法确定
于是去死磕题解
发现它的二维是这个点由什么速率转换而来的，这是唯一确定的
push进队列里的才讨论用自己的速率还是延续上一轮的速率
其实相比普通的dij
就是多了一维速率，其他是一样的
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef long long ll;
struct Edge {
ll to, w;
};
struct Node {
ll pos, w, s;
bool operator<(const Node &x) const {
return w > x.w;
}
} last;
vector<Edge> G[N];
priority_queue<Node> heap;
ll t, n, m, u, v, w, s[N], dis[N][N], vis[N][N];
inline ll Dijkstra() {
heap.push({1, 0, s[1]});
while (!heap.empty()) {
last = heap.top(), heap.pop();
for (auto edge : G[last.pos]) {
const ll ns = last.s, u = edge.to;
if (dis[u][ns] > last.w + edge.w * ns) {
dis[u][ns] = last.w + edge.w * ns;
heap.push({u, dis[u][ns], ns});
heap.push({u, dis[u][ns], s[u]});
}
}
}
ll minn = LLONG_MAX;
for (int i = 1; i <= 1000; i++) {
minn = min(minn, dis[n][i]);
}
return minn;
}
void solve() {
cin >> n >> m;
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0x00, sizeof(vis));
for (int i = 1; i <= n; i++) G[i].clear();
for (int i = 1; i <= m; i++) {
cin >> u >> v >> w;
G[u].push_back({v, w});
G[v].push_back({u, w});
}
for (int i = 1; i <= n; i++) {
cin >> s[i];
}
cout << Dijkstra() << '\n';
}
int main() {
cin >> t;
while (t--) solve();
return 0;
}