Untitled
plain_text
22 days ago
2.1 kB
2
Indexable
Never
#include<unordered_map> #include<vector> #include<iostream> #include<algorithm> #include<queue> using namespace std; vector<int> grid[55]; unordered_map<string, int> rest; unordered_map<int, vector<string>> ump; unordered_map< string,int> value; int vis[55]; int dis[55]; int n,m; void init(int N, int M, int mRoads[][2]) { n = N; m = M; rest.clear(); ump.clear(); value.clear(); for (int i = 0; i < 55; i++) { grid[i].clear(); } for (int i = 0; i < M; i++) { grid[mRoads[i][0]].push_back(mRoads[i][1]); grid[mRoads[i][1]].push_back(mRoads[i][0]); } } void addRestaurant(int mCityID, char mName[]) { ump[mCityID].push_back(mName); rest[mName] = 0; } void addValue(char mName[], int mScore) { string temp = mName; rest[mName] += mScore; int len = temp.length(); for (int i = 0; i < len; i++) { for (int j = 1;i+j <= len; j++) { string sub = temp.substr(i, j); value[sub] = max(value[sub], rest[mName]); } } } int bestValue(char mStr[]) { return value[mStr]; } int regionalValue(int mCityID, int mDist) { vector<int> top; queue<int> q; for (int i = 0; i <= n; i++) { vis[i] = 0; dis[i] = 999999; } vis[mCityID] = 1; dis[mCityID] = 0; q.push(mCityID); while (!q.empty()) { int node = q.front(); q.pop(); for (auto x : grid[node]) { if (vis[x] != 1 && dis[node] < mDist) { vis[x] = true; dis[x] = dis[node]+1; q.push(x); } } for (auto y : ump[node]) { top.push_back(rest[y]); } } int sum = 0; if (top.size() < 3) { for (int i = 0; i < top.size(); i++) { sum += top[i]; } return sum; } sort(top.begin(), top.end(), greater<int>()); for (int i = 0; i < 3; i++) { sum += top[i]; } return sum; }