题目链接
简单描述一下题意:
给定n个点,m条带权无向边,每个点i有一辆速度系数为Si的自行车。每经过一个点即可拥有该点的自行车,在任意两点之间路过的消耗为:已经拥有的某辆自行车的速度Si * 边权Wi,求从1号点到n号点的最小消耗。
思路:
因为需要求的是最小的总消耗,所以在某个点出发时,我们所选用的自行车的S肯定是越小越好的,此处可以贪心考虑。
我们重构一下这个图,把到达每个点时的状态(即当前所拥有的最小的)也考虑进来,
组建一个新的节点u:<节点编号u,状态stateU = min(statePre, s[u])>
所有的u的可达节点v从原题目读入的可达路径中重构,
在加入状态表示以后变为:<节点编号v,状态stateV = min(stateU, s[v])>
此时再对重构图使用dijkstra即可,起点为<1号节点,s[1]>。
void solve()
{
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> g(n);
vector<int> s(n);
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
g[a - 1].push_back({b - 1, c});
g[b - 1].push_back({a - 1, c});
}
for (auto &p : s) {
cin >> p;
}
auto dijkstra = [&]() -> int {
vector<vector<bool>> isUsed(n, vector<bool>(1001, false));
// <targetNode, minSi>
vector<vector<int>> dist(n, vector<int>(1001, 1e18));
dist[0][s[0]] = 0;
// <currentDist, currentNode>
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> hp;
hp.push({0, 0, s[0]});
while (!hp.empty()) {
auto [curDist, curNode, minS] = hp.top();
hp.pop();
if (isUsed[curNode][minS]) {
continue;
}
isUsed[curNode][minS] = true;
for (auto &[nextNode, weight] : g[curNode]) {
int nextS = min(minS, s[nextNode]);
if (dist[nextNode][nextS] >= curDist + weight * minS) {
dist[nextNode][nextS] = curDist + weight * minS;
hp.push({dist[nextNode][nextS], nextNode, nextS});
}
}
}
return *min_element(dist[n - 1].begin(), dist[n - 1].end());
};
cout << dijkstra() << endl;
}
标签:dist,短路,nextNode,单源,Bicycles,vector,nextS,minS,hp
From: https://www.cnblogs.com/whysopt/p/17936708