CSES PROBLEM: FLIGHT DISCOUNT...help needed

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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

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

Показать архивные | Написать комментарий?

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.

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