CSES Flight Discount

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

Автор -VIBE, история, 10 месяцев назад, По-английски

Was solving this Cses problem from graph section.I came up with a dp approach for this but getting wrong answer on three testcases.Can anyone help me in where i am going wrong. Here is my submission

cses graph

-VIBE
10 месяцев назад
7

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

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

MiyawakiSakura

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

Flight discount is a template problem for this algorithm:

algorithm

I can't open Ideone links, could you use another method of sharing such as linking to your submission on cases or posting to Pastebin?

Given that the intended solution is the algorithm above, I'm not sure how you can solve it with a dp approach, but I am really interested to see your approach!

→ Ответить

-VIBE

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

here

→ Ответить

MiyawakiSakura

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

Thanks a lot!

Looking at your program, it seems like you have a 1d DP where you try to find the min cost between using the coupon at that node and not using the coupon at that node.

One immediate problem I see is how you are managing the visited array. There may be multiple paths to any given airport, but you only allow yourself to visit an airport once. Therefore, your DP solution breaks because, at any given node, you do not know the shortest path to that node, nor the shortest path to the final node.

There are a few other problems, but we can work on this one first.

→ Ответить

_rey

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

Your dp fails at this case

do[4][0] will be 1e18 instead of 3. Your dp fails on cycles, such as the example I gave. You need to run Dijkstra's algorithm to solve this problem. CP algorithms has a very good tutorial on it.

→ Ответить

KyoumaHououin

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

His code may be wrong, but the test case you gave is running perfectly fine.

→ Ответить

_rey

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

It's numbered from 0 to n-1, but the problem gives numbers from 1 to n. If you add 1 to every element, his code outputs 62, which is incorrect, since there's a path that costs 54. Here's the fixed test case:

Here's an illustration fo the graph. You use the coupon on the edge from 1 to 2, then follow the path 1, 2, 5, 3, 4, 6.

Image

→ Ответить

kinitic013

4 месяца назад, # |

My submission getting TLE on Test 18 can someone help me with my code where can I optimize this code submission

mySubmission

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define endl '\n'
#define mp make_pair
#define mii map<ll, ll>
#define pii pair<ll, ll>
#define vi vector<ll>
#define vvi vector<vi>
#define vb vector<bool>
#define pii_pq_min  
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define REP(i, a, b) for (ll i = a; i < b; i++)
#define MOD (ll)(1e9 + 7)
#define mod (ll)998244353
void fast()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
long long my_sqrt(long long a)
{
    long long l=0,r=5000000001;
    while(r-l>1)
    {
        long long mid=(l+r)/2;
        if(1ll*mid*mid<=a)l=mid;
        else r=mid;
    }
    return l;
}
bool cmps(pii &a, pii &b)
{
    return a.ss < b.ss;
}
void solve()
{
    ll n,m;cin>>n>>m;
    // vector<pair<pii,ll>> edge(m);
    vector<vector<pii>> adj(n+1);
    REP(i,0,m)
    {
        ll u,v,w;cin>>u>>v>>w;
        // edge.pb({{u,v},w});
        adj[u].pb({v,w});
    }
    vi noDiscount(n+1,LONG_LONG_MAX);
    vi discount(n+1,LONG_LONG_MAX);
    discount[1] = 0;
    noDiscount[1] = 0;
    auto compare = [](const pair<ll, pair<ll, ll>>& a, const pair<ll, pair<ll, ll>>& b) {
        return a.first > b.first;  // Change to a.first < b.first for minimum priority
    };
 
    // Declare a priority queue with the custom comparison function
    priority_queue<pair<ll, pair<ll, ll>>, vector<pair<ll, pair<ll, ll>>>, decltype(compare)> q(compare);
    // priority_queue<pair<ll,pii> , vector<pair<ll,pii>>, greater<pii>> q;
    q.push({0,{1,1}});
    q.push({0,{1,0}});
    vb discountVisited(n+1,false);
    vb noDiscountVisited(n+1,false);
    ll countDiscount = 0;
    ll countNoDiscount = 0;
    while(!q.empty())
    {
        ll prevDistance = q.top().ff;
        ll isDiscounted = q.top().ss.ss;
        ll u = q.top().ss.ff;
 
        if(discountVisited[u] && noDiscountVisited[u]){
            q.pop();
            continue;
        }
        if(isDiscounted)
        {
            countDiscount++;
            discountVisited[u] = 1;
        }
        else
        {
            noDiscountVisited[u] = 1;
            countNoDiscount++ ;
        }
        
        for (auto x : adj[u])
        {
            if(isDiscounted)
            {
                if(prevDistance + x.ss < discount[x.ff])
                {
                    discount[x.ff] = min<ll>(discount[x.ff] , prevDistance + x.ss);
                    q.push({discount[x.ff],{x.ff,1}}) ; 
                }
                
            }
            else
            {
                //current discounted
                ll currentDiscounted = prevDistance + x.ss/2 ;
                if(currentDiscounted < discount[x.ff])
                {
                    discount[x.ff] = currentDiscounted ;
                    q.push({discount[x.ff],{x.ff,1}});
                }
                // no discount 
                ll currentCost = prevDistance + x.ss;
                if(currentCost < noDiscount[x.ff])
                {
                    noDiscount[x.ff] = currentCost;
                    q.push({noDiscount[x.ff],{x.ff,0}});
                }
            }
        }
        q.pop();
        if(countNoDiscount == n && countDiscount == n)
        break;
    }
 
    cout<<discount[n];
    return;
}
int main()
{
    fast();
    // ll t;
    // cin >> t;
    // while (t--)
    {
        solve();
        cout << endl;
    }
    return 0;
}

→ Ответить