算法——图论——最短路径(多边权)
原题
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
vector<int> cityIndex(100, 0);
vector<PII> graph[100];
vector<int> Dist(100, -1);
vector<bool> State(100, false);
vector<int> lastNode[100];
struct pqNode {
int destination;
int dist;
int lastNode;
pqNode(int destination_, int dist_, int lastNode_) : destination(destination_), dist(dist_), lastNode(lastNode_) {}
};
struct compare {
bool operator()(pqNode lhs, pqNode rhs) {
return lhs.dist > rhs.dist;
}
};
vector<vector<int>> Paths;
vector<int> tmpPath;
void dfs(int s, int t) {
if (s == t) {
tmpPath.push_back(s);
Paths.push_back(tmpPath);
tmpPath.pop_back();
return;
}
for (int last: lastNode[t]) {
tmpPath.push_back(t);
dfs(s, last);
tmpPath.pop_back();
}
}
void Dijkstra(int s) {
Dist[s] = 0;
priority_queue<pqNode, vector<pqNode>, compare> pq;
pq.push(pqNode(s, 0, s));
while (!pq.empty()) {
auto cur = pq.top();
pq.pop();
if (State[cur.destination]) {
if (cur.dist == Dist[cur.destination])
lastNode[cur.destination].push_back(cur.lastNode);
continue;
} else {
State[cur.destination] = true;
lastNode[cur.destination].push_back(cur.lastNode);
}
for (auto neighbor: graph[cur.destination]) {
if (Dist[neighbor.first] >= Dist[cur.destination] + neighbor.second || Dist[neighbor.first] == -1) {
Dist[neighbor.first] = Dist[cur.destination] + neighbor.second;
pq.push(pqNode(neighbor.first, Dist[neighbor.first], cur.destination));
}
}
}
}
bool pathCompare(vector<int> lhs, vector<int> rhs) {
float l = 0, r = 0;
for (int city: lhs) {
l += (float)cityIndex[city];
}
for (int city: rhs) {
r += (float )cityIndex[city];
}
l = l / (float )lhs.size();
r = r / (float )rhs.size();
return l <= r;
}
int main() {
int n, m, s, t;
cin >> n >> m >> s >> t;
for (int i = 0; i < n; ++i) {
cin >> cityIndex[i];
}
// 建图
for (int i = 0; i < m; ++i) {
int u, v, d;
cin >> u >> v >> d;
graph[u].push_back({v, d});
graph[v].push_back({u, d});
}
Dijkstra(s);
dfs(s, t);
sort(Paths.begin(), Paths.end(), pathCompare);
vector<int> result = Paths.front();
reverse(result.begin(), result.end());
cout << Dist[t] << " ";
for (int i = 0; i < result.size(); ++i) {
if (i != result.size() - 1) {
cout << result[i] << "->";
}else{
cout << result[i] << endl;
}
}
return 0;
}