AcWing 1577. 条条大路通罗马
原题链接
中等
作者:
RainSure
,
2022-02-28 16:53:22
,
所有人可见
,
阅读 163
以后梦里全是unordered_map
#include<iostream>
#include<cstring>
#include<vector>
#include<unordered_map>
#include<queue>
#include<algorithm>
using namespace std;
#define x first
#define y second
const int inf = 0x3f3f3f3f;
typedef pair<int, string> PIS;
unordered_map<string, vector<pair<string, int>>> v;
unordered_map<string, int> w, dist, happy, cnt, sum;
unordered_map<string, string> pre;
unordered_map<string, bool> st;
int n, m;
string s;
void Dijkstra()
{
for(auto item : w) dist[item.x] = inf;
dist[s] = 0;
cnt[s] = 1;
priority_queue<PIS, vector<PIS>, greater<PIS>> heap;
heap.push({0, s});
while(heap.size())
{
auto t = heap.top();
heap.pop();
string u = t.y;
if(st[u]) continue;
st[u] = true;
for(int i = 0; i < v[u].size(); i ++){
auto j = v[u][i].x;
auto distance = v[u][i].y;
if(dist[j] > dist[u] + distance){
dist[j] = dist[u] + distance;
pre[j] = u;
cnt[j] = cnt[u];
happy[j] = happy[u] + w[j];
sum[j] = sum[u] + 1;
cnt[j] = cnt[u];
heap.push({dist[j], j});
}
else if(dist[j] == dist[u] + distance){
cnt[j] += cnt[u];
if(happy[j] < happy[u] + w[j]){
happy[j] = happy[u] + w[j];
sum[j] = sum[u] + 1;
pre[j] = u;
}
else if(happy[j] == happy[u] + w[j]){
if(sum[j] > sum[u] + 1){
sum[j] = sum[u] + 1;
pre[j] = u;
}
}
}
}
}
}
int main()
{
cin >> n >> m >> s;
for(int i = 0; i < n - 1; i ++){
string a;
int b;
cin >> a >> b;
w[a] = b;
}
while(m --)
{
string a, b;
int c;
cin >> a >> b >> c;
v[a].push_back({b, c});
v[b].push_back({a, c});
}
Dijkstra();
string e = "ROM";
cout << cnt[e] << " " << dist[e] << " " << happy[e] << " " << happy[e] / sum[e] << endl;
vector<string> res;
while(e != s){
res.push_back(e);
e = pre[e];
}
res.push_back(s);
reverse(res.begin(), res.end());
for(int i = 0; i < res.size(); i ++){
if(i != 0) cout << "->";
cout << res[i];
}
return 0;
}