CSES PROBLEM: FLIGHT DISCOUNT...help needed

№	Пользователь	Рейтинг
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	161
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	SecondThread	147
9	orz	146
10	pajenegod	145

https://cses.fi/problemset/task/1195 to solve this problem i implemented dijkstra's and Dynamic Programming to decide whether to opt for coupon or not for each state transiton.But I'am getting TLE and not able to optimize my code. I think my approach is slow. Any suggestion please help. Here is william lin's code https://youtu.be/dZ_6MS14Mg4?t=13603 but i did't get his approach. If any one could explain what he did will be helpful

My Code

#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define _FAST   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int32_t main()
{
    _FAST
    int n, m;
    cin >> n >> m;
    vector<vector<int>> edges[n + 1];
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edges[a].push_back({b, c});
    }
 
    vector<vector<int>> dist(n + 1, vector<int>(2, 1e16));
    set<vector<int>> s;
    s.insert({0,1});
 
    dist[1][0]=dist[1][1]=0;
 
    while (s.size())
    {
        vector<int> temp = *s.begin();
        s.erase(s.begin());
 
        int i = temp[1];
 
        for (vector<int> &J: edges[i])
        {
            int j = J[0];
            int now_cost = J[1];
 
            int old1 = dist[j][0];
            int old2 = dist[j][1];
 
            dist[j][0] = min(dist[j][0], dist[i][0] + now_cost);
            dist[j][1] = min({dist[j][1], dist[i][1] + now_cost, dist[i][0] + now_cost / 2});
            
            auto it=s.find({old1, j});
            auto jt=s.find({old2, j});
            
            if (old1 != dist[j][0]  && it!=s.end())
                s.erase(it);
            else
                s.insert({dist[j][0], j});
            if (old2 != dist[j][1] && jt!=s.end())
                s.erase(jt);
            else
                s.insert({dist[j][1], j});
        }
    }
    cout << min(dist[n][1], dist[n][0]);
    return 0;
}

/** * Dont raise your voice, improve your argument. * --Desmond Tutu */ #include <bits/stdc++.h> using namespace std; const bool ready = [](){ ios_base::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(12); return true; }(); const double PI = acos(-1); using ll= long long; #define int ll #define fori(n) for(int i=0; i<int(n); i++) #define cini(i) int i; cin>>i; #define cins(s) string s; cin>>s; #define cind(d) double d; cin>>d; #define cinai(a,n) vi a(n); fori(n) { cin>>a[i]; } #define cinas(s,n) vs s(n); fori(n) { cin>>s[i]; } #define cinad(a,n) vd a(n); fori(n) { cin>>a[i]; } using pii= pair<int, int>; using pdd= pair<double, double>; using vd= vector<double>; using vb= vector<bool>; using vi= vector<int>; using vvi= vector<vi>; using vs= vector<string>; const int INF=4e18; void solve() { cini(n); cini(m); vector<vector<pii>> adj(n); for(int i=0; i<m; i++) { cini(a); a--; cini(b); b--; cini(w); adj[a].emplace_back(b,w); } vvi dp(2, vi(n, INF)); /* dp[0] without using coupon, dp[1] with using coupon */ dp[0][0]=0; dp[1][0]=0; priority_queue<pii> q; q.emplace(0,0); while(q.size() && -q.top().first<max(dp[0][n-1], dp[1][n-1])) { int node=q.top().second; q.pop(); for(auto chl : adj[node]) { bool pu=false; if(dp[0][chl.first]>dp[0][node]+chl.second) { dp[0][chl.first]=dp[0][node]+chl.second; pu=true; } if(dp[1][chl.first]>dp[1][node]+chl.second) { dp[1][chl.first]=dp[1][node]+chl.second; pu=true; } if(dp[1][chl.first]>dp[0][node]+(chl.second/2)) { dp[1][chl.first]=dp[0][node]+(chl.second/2); pu=true; } if(pu) q.emplace(-dp[1][chl.first], chl.first); } } cout<<min(dp[1][n-1], dp[0][n-1])<<endl; } signed main() { solve(); }

Комментарии (16)

Написать комментарий?

Kartik_Bhanderi

4 года назад, # |

← Rev. 6 →

Here's my approach...

-Firstly find shortest path from 1 to every node. (answers in array A)

-Then find shortest path from N to every node (on Inverted graph) which means finding shortest path from every node to N.(answers in array B)

-Then consider each edge(u,v) in graph , suppose you are applying discount on that edge... then if we can reach 1 to u and N to v (in short v to N) then ans=min( ans , A[u] + weight/2 + B[v] )...

→ Ответить

naveenk2k

4 года назад, # ^ |

← Rev. 2 →

@Kartik_Bhanderi

Thanks for your input. I tried following your approach and wrote the following code:

My code

#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvl;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<long long, long long>> vpl;
typedef pair<int, int> pi;
typedef pair<long long, long long> pl;

#define PB push_back
#define MP make_pair
#define REP(i, a, b) for (ll i = a; i <= (ll)b; i++)
#define REPR(i, a, b) for (ll i = a; i >= (ll)b; i--)
#define show(arr)                            \
    cerr << #arr << " is:"                   \
         << "\n[ ";                          \
    for (auto& ax : arr) cout << ax << ", "; \
    cout << "]\n\n";
#define disp(x) cerr << #x << " is " << x << "\n";
#define bm(x) cout << "!Here" << x << "!" \
                   << "\n";
#define en "\n"
#define INF 1000000007

void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int testCases = 1;
    // cin >> testCases;
    while (testCases--) solve();

    return 0;
}

void solve() {
    ll n, m;
    cin >> n >> m;

    vector<tuple<ll, ll, ll>> edges(m);
    for (auto& [a, b, w] : edges) cin >> a >> b >> w;

    vl distFrom1(n + 1, INF), distFromN(n + 1, INF);
    distFrom1[1] = distFromN[n] = 0;

    REP(i, 0, n - 1) {
        for (auto [a, b, w] : edges) {
            distFrom1[b] = min(distFrom1[b], distFrom1[a] + w);
            distFromN[a] = min(distFromN[a], distFromN[b] + w);
        }
    }

    ll ans = INF;
    for (auto [a, b, w] : edges)
        ans = min(ans, distFrom1[a] + (w / 2) + distFromN[b]);

    cout << ans << en;
}

However, I still seem to get TLE on the majority of test cases. Is this only because I've implemented Bellman-Ford instead of Dijkstra or would you refactor my current code to be more efficient?

← Rev. 5 →

Firstly put your code in spoiler properly. (for that choose spoiler and inside that choose block and place your code there...)

Like this

And as you said you have implemented bellmen ford , whose time complexity is O(V.E) , so obviously it will result into TLE.

And in our case we only need single source shortest path , hence no need to use bellman ford instead we can use dijkstra's algo.

Hope it helps ;)

Sorry about that; I've fixed the formatting now.

And yes, I thought so too. Thanks for the confirmation. I'll try to learn Dijkstra's and implement it now!

Good.

akashtadwai

3 года назад, # ^ |

Hi Kartik_Bhanderi I got TLE in 4 cases by using Dijkstra too!

Can you please check if anything went wrong?

Code


#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define INF LLONG_MAX
#define ar array
#define arr ar<int, 2>
#define IOS                         \
  std::ios::sync_with_stdio(false); \
  cin.tie(NULL);

int n, m;

vector<int> dijkstra(int v, vector<vector<ar<int, 2>>> &g)
{

  priority_queue<arr, vector<arr>, greater<arr>> pq;
  vector<int> dis(n, INF);
  dis[v] = 0;
  pq.push({v, 0});
  while (!pq.empty())
  {
    auto tp = pq.top();
    pq.pop();
    int dist = tp[1];
    if (dis[tp[0]] != dist)
      continue;

    for (auto v : g[tp[0]])
    {
      int ver = v[0], weight = v[1];
      if (dis[ver] > dis[tp[0]] + weight)
      {
        dis[ver] = dis[tp[0]] + weight;
        pq.push({ver, dis[ver]});
      }
    }
  }
  return dis;
}
void init()
{
  cin >> n >> m;
  vector<vector<ar<int, 2>>> g, grev;
  vector<ar<int, 3>> edges;
  g.resize(n), grev.resize(n);
  for (int i = 0; i < m; i++)
  {
    int u, v, w;
    cin >> u >> v >> w;
    --u, --v;
    g[u].pb({v, w});
    grev[v].pb({u, w});
    edges.pb({u, v, w});
  }
  vector<int> a = dijkstra(0, g);
  vector<int> b = dijkstra(n - 1, grev);

  int ans = INF;

  for (auto edge : edges)
  {
    int st = edge[0], end = edge[1];
    if (a[st] != INF and b[end] != INF)
    {
      ans = min(ans, b[end] + a[st] + edge[2] / 2);
    }
  }
  cout << ans << endl;
}
int32_t main()
{
  IOS;
  init();
  return 0;
}

jeroenodb

Why do you put the array (node,distance) in the priority queue, shouldn't it be the other way around to correctly sort distance first? I think that could be your problem.

Use long long only when it's needed
Try scanf to take input

Your logic also seems to be wrong, in priority queue it shoud be (dist,node).

Lextor99

Sir, can you please explain what is 'u' and what is 'v'?

Both represent Node.

From answer's context : there is an edge between node u and node v.

hussainafroz903

8 месяцев назад, # ^ |

can you share your code it will be very much helpful in implementation part or any one on using the (*mentioned) approach

spookywooky

← Rev. 3 →

I got same aproach as yours, but use priority_queue instead of set. And I do not erase any extra element from the queue at any time. Just put new vertex on the queue whenever one of the dp-values becomes smaller.

Spoiler

Sumanto

By adding negative values of DP you are priority queue work as min_heap?

Yes, this is just to make the priority_queue.top() work like set.begin(), ie return the smallest element.

Is it safe to assume that set operations are more expensive than operations on priority queue?

Yes, of course, especially write access is more expensive. Same O(logn), but bigger constant factor.

Блог пользователя Sumanto