PROBLEM LINK:
DIFFICULTY:
MEDIUM
PREREQUISITES:
Shortest Paths with Non-Negative Edge Weights or Dijkstra Algorithm, Greedy, Heaps
EXPLANATION:
Say we use the voucher on the edge between cities A and B.
There are two cases: we can go from 1→A→B→N or 1→B→A→N. We need to know the distance between 1 and A, and B and N.
We can use Dijkstra’s to compute the distance from 1 and N to every vertex. Then our answer is \min\limits_{A\rightarrow B} \texttt{dist1}[A]+c(A,B)+\texttt{distN}[B], where c(A,B) is the cost to travel from city A to city B after applying the voucher to that flight, \texttt{dist1}[A] is the cost to travel from city 1 to city A and \texttt{distN}[A] is the cost to travel from city B to city N.
Checkout the work function:
SOLUTIONS:
Solution
// Disclaimer: Don't copy my template, it may lead to plagiarism.
/* Author: Soumy Jain
Handle: soumy_jain || soumyjain
"Beautiful flowers too, eventually wither and fall. That's the fate of all living beings."
"I hate perfection. To be perfect is to be unable to improve any further." - Mayuri Kurotsuchi | Bleach
"I smile to show the pressure of heroes and to trick the fear inside of me."
"Gravel may be gravel, but me? I'm the gravel that shatters diamonds."
"If you were to write a story with me in the lead role, it would certainly be...a TRAGEDY." - Kaneki Ken | Tokyo
Ghoul
*/
/******************************************************************************/
// clang-format off
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define SPEEDHACK ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ff first
#define ss second
#define sz(v) (ll)(v).size()
#define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define MOD 1000000007 // 998244353
using namespace std;
/******************************************************************************/
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(ll x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(ull x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template<typename T, typename V>
void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}'; }
template<typename T>
void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}"; }
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
// clang-format on
/***********************************MAIN***************************************/
// Are you ready to face the wrath of test cases? Good luck Soumy!
void work()
{
ll n, m;
cin >> n >> m;
vector<vector<pair<ll, ll>>> vg1(n), vg2(n);
for (int i = 0; i < m; i++)
{
ll u, v, c;
cin >> u >> v >> c;
u--, v--;
vg1[u].push_back({v, c});
vg2[v].push_back({u, c});
}
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
vector<ll> d1(n, LLONG_MAX), dn(n, LLONG_MAX);
d1[0] = 0;
pq.push({0, 0});
while (sz(pq))
{
auto [d, u] = pq.top();
pq.pop();
for (auto [v, c] : vg1[u])
{
if (d + c < d1[v])
{
d1[v] = d + c;
pq.push({d1[v], v});
}
}
}
dn[n - 1] = 0;
pq.push({0, n - 1});
while (sz(pq))
{
auto [d, u] = pq.top();
pq.pop();
for (auto [v, c] : vg2[u])
{
if (d + c < dn[v])
{
dn[v] = d + c;
pq.push({dn[v], v});
}
}
}
ll ans = LLONG_MAX;
for (int u = 0; u < n; u++)
{
if (d1[u] != LLONG_MAX)
for (auto [v, c] : vg1[u])
{
if (dn[v] != LLONG_MAX)
ans = min(ans, d1[u] + c / 2 + dn[v]);
}
}
cout << ans;
}
int main()
{
SPEEDHACK
// file
ll t = 1;
// cin >> t;
while (t--)
{
work();
}
return 0;
}