CSES PROBLEM: FLIGHT DISCOUNT...help needed

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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(); }

Comments (15)

Show archived | Write comment?

Kartik_Bhanderi

4 years ago, # |

← 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] )...

→ Reply

naveenk2k

4 years ago, # ^ |

← 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 years ago, # ^ |

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.

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's blog