Skip to content

Instantly share code, notes, and snippets.

@medhruv7
Created May 22, 2020 20:26
Show Gist options
  • Save medhruv7/89cd2f9c3c23d496d1209af62e172abc to your computer and use it in GitHub Desktop.
Save medhruv7/89cd2f9c3c23d496d1209af62e172abc to your computer and use it in GitHub Desktop.
//dhruv
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ll long long
#define ffor(i,n) for(int i = 0;i < (n); ++i)
#define fro(i,j,n) for(int i = (j);i < (n); ++i)
#define all(v) v.begin(),v.end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define ff first
#define ss second
const int mod = 1e9 + 7;
template<typename T>
T binpow(T a,T b,T mod){
T res = 1;
while(b){
if(b&1){
res = (res*a)%mod;
}
b /= 2;
(a *= a) %= mod;
}
return res;
}
template<typename T>
T binpow(T a,T b){
T res = 1;
while(b){
if(b&1){
res = (res*a);
}
b /= 2;
a *= a;
}
return res;
}
template<typename T>
T add(T a,T b){
return (a + b)%mod;
}
template<typename T>
T sub(T a,T b){
return add(a,mod - b);
}
template<typename T>
T mul(T a,T b){
return (a*b)%mod;
}
int make_int(string s){
int x = 0;
reverse(s.begin(),s.end());
string tmp = s;
for(int i = 0;i < s.length(); ++i){
x *= 10;
x += (int)(tmp.back() - '0');
tmp.pop_back();
}
return x;
}
string make_string(int s){
string x;
while(s){
x.push_back(char(s%10 + '0'));
s /= 10;
}
reverse(x.begin(),x.end());
return x;
}
const ll inf = 1e18;
const int mxn = 1e5 + 10;
const int mxm = 2e5 + 10;
int n,m;
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq,pq2;
vector<pair<int,int>> adj[mxn],adj2[mxn];
void diks(ll dist[]){
pq.push({0,0});
while(!pq.empty()){
auto tp = pq.top();
int from = tp.ff;
ll dst = tp.ss;
pq.pop();
if(dist[from] < dst) continue;
for(auto x : adj[from]){
int to = x.ff;
ll cst = x.ss;
if(dist[from] + cst < dist[to]){
pq.push({to,dist[from] + cst});
dist[to] = dist[from] + cst;
}
}
}
}
void diks2(ll dist2[]){
pq2.push({n - 1,0});
while(!pq2.empty()){
auto tp = pq2.top();
int from = tp.ff;
ll dst = tp.ss;
pq2.pop();
if(dist2[from] < dst) continue;
for(auto x : adj2[from]){
int to = x.ff;
ll cst = x.ss;
if(dist2[from] + cst < dist2[to]){
pq2.push({to,dist2[from] + cst});
dist2[to] = dist2[from] + cst;
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
vector<pair<pair<int,int>,int>> edge(m);
ll dist[n],dist2[n];
ffor(i,n){
dist[i] = inf;
dist2[i] = inf;
}
ffor(i,m){
int x,y,z;
cin >> x >> y >> z;
--x,--y;
adj[x].push_back({y,z});
adj2[y].push_back({x,z});
edge[i] = {{x,y},z};
}
dist[0] = 0;
dist2[n - 1] = 0;
diks(dist);
diks2(dist2);
ll r = dist[n - 1];
// cout << dist[n - 1];
ffor(i,m){
int x = edge[i].ff.ff;
int y = edge[i].ff.ss;
int z = edge[i].ss;
r = min(dist[x] + dist2[y] + z/2,r);
}
cout << r;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment