### Sumanto's blog

By Sumanto, 13 months ago,

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

• -2

 » 13 months ago, # | ← Rev. 3 →   +5 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 consdier each edge 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] )...
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 Thanks for your input. I tried following your approach and wrote the following code: My code#include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector vi; typedef vector vl; typedef vector> vvi; typedef vector> vvl; typedef vector> vpi; typedef vector> vpl; typedef pair pi; typedef pair 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> 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?
•  » » » 13 months ago, # ^ | ← Rev. 4 →   +2 Brother , firstly put your code in spoiler properly. (for that choose spoiler and inside that choose block and place your code there...) Like thisinclude include include include include include include include include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef vector vi; typedef vector vl; typedef vector vvi; typedef vector vvl; typedef vector> vpi; typedef vector> vpl; typedef pair pi; typedef pair 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> 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; }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 ;)
•  » » » » 13 months ago, # ^ |   +2 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!
•  » » » » » 13 months ago, # ^ | ← Rev. 2 →   +2 Good.
•  » » » » » » 5 weeks ago, # ^ |   0 Hi Kartik_Bhanderi I got TLE in 4 cases by using Dijkstra too!Can you please check if anything went wrong? Code#include using namespace std; #define pb push_back #define int long long #define INF LLONG_MAX #define ar array #define arr ar #define IOS \ std::ios::sync_with_stdio(false); \ cin.tie(NULL); int n, m; vector dijkstra(int v, vector>> &g) { priority_queue, greater> pq; vector 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>> g, grev; vector> 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 a = dijkstra(0, g); vector 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; } 
•  » » » » » » » 5 weeks ago, # ^ |   +3 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.
•  » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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).
 » 13 months ago, # | ← Rev. 3 →   0 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/** * Dont raise your voice, improve your argument. * --Desmond Tutu */ #include 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>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; using pdd= pair; using vd= vector; using vb= vector; using vi= vector; using vvi= vector; using vs= vector; const int INF=4e18; void solve() { cini(n); cini(m); vector> adj(n); for(int i=0; i q; q.emplace(0,0); while(q.size() && -q.top().firstdp[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<
•  » » 13 months ago, # ^ |   0 By adding negative values of DP you are priority queue work as min_heap?
•  » » » 13 months ago, # ^ |   0 Yes, this is just to make the priority_queue.top() work like set.begin(), ie return the smallest element.
•  » » » » 13 months ago, # ^ |   0 Is it safe to assume that set operations are more expensive than operations on priority queue?
•  » » » » » 13 months ago, # ^ |   0 Yes, of course, especially write access is more expensive. Same O(logn), but bigger constant factor.