salt_n_ice's blog

By salt_n_ice, history, 2 months ago, In English

Pproblem: Link. I have already seen the

Solution

and I did the required changes. But still, there are 3 test cases that are not passing.

Code
 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

You Can Compare to my code.


// SACXY #include<bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // using namespace __gnu_pbds; using namespace std; #define ff first #define ss second #define int long long int #define pb push_back #define mp make_pair #define pii pair<int,int> #define vi vector<int> #define mii map<int,int> #define repp(i, a, b) for(int i = a; i <= b; i++) #define rep(i, a, b) for(int i = a; i < b; i++) #define rrep(i, b, a) for(int i = b; i >= a; i--) #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() #define lb lower_bound #define ub upper_bound #define endl "\n" #define setbits(x) __builtin_popcountll(x) #define zrobits(x) __builtin_ctzll(x) #define mod 1000000007 // #define inf 1e9 #define ps(x,y) fixed<<setprecision(y)<<x #define w(x) int x; cin>>x; while(x--) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define MAX 100005 const int inf = 1e18; void c_p_c() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif } int n,m; vector<pii> adj[MAX]; vector<pii> adj_in[MAX]; int32_t main() { c_p_c(); vector<tuple<int,int,int> > edges; cin >> n >> m; rep(i,0,m) { int x,y,wt; cin >> x >> y >> wt; adj[x].pb({y,wt}); adj_in[y].pb({x,wt}); // edges.pb({x,y,wt}); } vector<int> d(n+1,inf); vector<int> dn(n+1,inf); vector<int> par(n+1,-1); // par[1] = -1; d[1] = 0; priority_queue<pii,vector<pii>,greater<pii> > q; q.push({0,1}); while(!q.empty()) { int v = q.top().ss; int d_v = q.top().ff; q.pop(); if(d_v != d[v]) continue; for(auto edge: adj[v]) { int to = edge.ff; int len = edge.ss; if(d[to] > d[v] + len) { d[to] = d[v] + len; // par[to] = v; q.push({d[to],to}); } } } dn[n] = 0; priority_queue<pii,vector<pii>,greater<pii> > qn; qn.push({0,n}); while(!qn.empty()) { int v = qn.top().ss; int d_v = qn.top().ff; qn.pop(); if(d_v != dn[v]) continue; for(auto edge: adj_in[v]) { int to = edge.ff; int len = edge.ss; if(dn[to] > dn[v] + len) { dn[to] = dn[v] + len; // par[to] = v; qn.push({dn[to],to}); } } } int ans = inf; repp(i,1,n) { for(auto j : adj[i]) { int a = i; int b = j.ff; int wt = j.ss; ans = min(d[a]+wt/2+dn[b],ans); } } cout << ans << endl; return 0; }