Join Us
Loading Similar Posts
Entering edit mode
Q : Taxi Company - My Solution
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, pair<int, int>>
int main()
{
int n, m;
cin >> n >> m;
unordered_map<int, vector<pii>> mp(n + 1); // u -> { v, {state, national} }
for (int i = 0; i < m; i++)
{
int u, v, state, national;
cin >> u >> v >> state >> national;
mp[u].push_back({v, {state, national}});
mp[v].push_back({u, {state, national}});
}
int city1, city2;
cin >> city1 >> city2;
priority_queue<pii, vector<pii>, greater<pii>> pq; // dist , node , usedNational
vector<vector<int>> dist(n + 1, vector<int>(2, 1e9)); // dist[node][usedNational]
pq.push({0, {city1, 0}});
dist[city1][0] = 0;
while (!pq.empty())
{
auto it = pq.top();
pq.pop();
int d = it.first;
int city = it.second.first;
int hasUsed = it.second.second;
for (auto adj : mp[city])
{
int v = adj.first;
int state = adj.second.first;
int national = adj.second.second;
if (hasUsed == 0)
{ // can use national or preserve it for future
if (dist[v][1] > d + national) // use national
{
dist[v][1] = d + national;
pq.push({dist[v][1], {v, 1}});
}
if (dist[v][0] > d + state) // preserve national
{
dist[v][0] = d + state;
pq.push({dist[v][0], {v, 0}});
}
}
else // have to use state as already used national
{
if (dist[v][1] > d + state)
{
dist[v][1] = d + state;
pq.push({dist[v][1], {v, 1}});
}
}
}
}
cout << dist[city2][1];
return 0;
}
Entering edit mode
Question 2 Solution
string formatRange(int lower, int upper) {
if (lower == upper) return to_string(lower);
return to_string(lower) + "->" + to_string(upper);
}
vector<string> findMissingRanges(vector<int>& A, int lower, int upper) {
vector<string> ans;
int i = lower, j = 0, N = A.size();
while (j < N) {
if (i == A[j]) {
++i;
++j;
} else {
int first = i, last = A[j] - 1;
ans.push_back(formatRange(first, last));
i = A[j++] + 1;
}
}
if (i <= upper) ans.push_back(formatRange(i, upper));
return ans;
}
void solve() {
int n;
cin>>n;
vector<int> v(n);
f(i,n)
cin>>v[i];
set<int> s;
for(int i=0;i<n;i++)
s.insert(v[i]);
vector<int> temp;
for(auto i:s)
temp.pb(i);
int low,high;
cin>>low>>high;
vector<string> ans;
ans=findMissingRanges(temp,low,high);
cout<<"[";
for(int i=0;i<(int)ans.size();i++)
{
if(i==int(ans.size()-1))
cout<<ans[i];
else
cout<<ans[i]<<",";
}
cout<<"]";
cout<<endl;
}
Entering edit mode
Question 3 Solution
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
const int INF = numeric_limits<int>::max();
struct Edge {
int to;
int dist1;
int dist2;
};
void dijkstra(int start, int end, const vector<vector<Edge>>& graph, vector<vector<int>>& distances) {
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
distances[start][0] = 0; // Using only state highway
distances[start][1] = 0; // Using national highway
pq.push(make_pair(0, make_pair(start, 0)));
while (!pq.empty()) {
int current_distance = pq.top().first;
int current = pq.top().second.first;
int usedNational = pq.top().second.second;
pq.pop();
if (current_distance > distances[current][usedNational])
continue;
for (const Edge& edge : graph[current]) {
int next = edge.to;
int new_distance = edge.dist1 + current_distance;
// Use only state highway
if (new_distance < distances[next][usedNational]) {
distances[next][usedNational] = new_distance;
pq.push(make_pair(new_distance, make_pair(next, usedNational)));
}
// Use national highway if not already used
if (!usedNational) {
int new_distance_with_national = max(min(edge.dist1, edge.dist2), current_distance);
if (new_distance_with_national < distances[next][1]) {
distances[next][1] = new_distance_with_national;
pq.push(make_pair(new_distance_with_national, make_pair(next, 1)));
}
}
}
}
}
int main() {
int N, M;
cin >> N >> M;
vector<vector<Edge>> graph(N + 1);
for (int i = 0; i < M; ++i) {
int a, b, dist1, dist2;
cin >> a >> b >> dist1 >> dist2;
graph[a].push_back({b, dist1, dist2});
graph[b].push_back({a, dist1, dist2});
}
int city1, city2;
cin >> city1 >> city2;
if (city1 >= city2) swap(city1, city2);
vector<vector<int>> distances(N + 1, vector<int>(2, INF));
dijkstra(city1, city2, graph, distances);
int minDistance = min(distances[city2][0], distances[city2][1]);
cout << "Minimum distance from city " << city1 << " to city " << city2 << " is: " << minDistance << endl;
return 0;
}
Entering edit mode
Question 1 Solution
bool isvowel(char c)
{
if(c=='a' || c=='e' || c=='i' || c=='o' || c=='u')
return true;
else
return false;
}
void solve() {
string s;
cin>>s;
int k;
cin>>k;
int v=0;
int n=s.length();
for(int i=0;i<k;i++)
{
if(isvowel(s[i]))
v++;
}
int ans=0;
ans=max(ans,v);
for(int i=k;i<n;i++)
{
if(isvowel(s[i-k]))
v--;
if(isvowel(s[i]))
v++;
ans=max(ans,v);
}
cout<<ans<<endl;
}
Entering edit mode
Q: Missing Range - My Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> arr;
for (int i = 0; i < n; i++)
{
int val;
cin >> val;
arr.push_back(val);
}
int l, h;
cin >> l >> h;
sort(arr.begin(), arr.end());
vector<string> res;
int i = l;
for (int i = 0; i < n; i++)
{
if (arr[i] - l > 0)
{ // missing range
if (arr[i] - 1 == l)
{
res.push_back(to_string(l));
}
else
{
res.push_back(to_string(l) + "->" + to_string(arr[i] - 1));
}
}
l = arr[i] + 1;
}
if (h - l > 0)
{ // missing range
if (h - 1 == l)
{
res.push_back(to_string(l));
}
else
{
res.push_back(to_string(l) + "->" + to_string(h));
}
}
for (auto it : res)
{
cout << it << " ";
}
cout << endl;
return 0;
}
