Last active
May 22, 2020 20:51
-
-
Save medhruv7/98e802016a9f9c34cbe3e7dc178c0dd4 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //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<ll> | |
| #define vvi vector<vi> | |
| #define pii pair<ll,ll> | |
| #define vpii vector<pii> | |
| #define ff first | |
| #define ss second | |
| #define pp priority_queue<pii,vpii,greater<pii>> | |
| 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 + 5; | |
| void dick(int src,vector<vpii> &adj,vi &dist){ | |
| pp pq; | |
| dist[src] = 0; | |
| pq.push({src,0}); | |
| while(!pq.empty()){ | |
| auto tp = pq.top(); | |
| ll from = tp.ff; | |
| ll dst = tp.ss; | |
| pq.pop(); | |
| if(dist[from] < dst)continue; | |
| for(auto x : adj[from]){ | |
| ll to = x.ff; | |
| ll cst = x.ss; | |
| if(dist[to] > dist[from] + cst){ | |
| dist[to] = dist[from] + cst; | |
| pq.push({to,dist[to]}); | |
| } | |
| } | |
| } | |
| } | |
| signed main(){ | |
| ios_base::sync_with_stdio(false); | |
| cin.tie(0); | |
| int n,m; | |
| cin >> n >> m; | |
| vector<pair<pii,ll>> edge; | |
| vector<vector<pii>> adj1(n),adj2(n); | |
| vi dist1(n,inf),dist2(n,inf); | |
| ffor(i,m){ | |
| int x,y,z; | |
| cin >> x >> y >> z; | |
| --x,--y; | |
| adj1[x].push_back({y,z}); | |
| adj2[y].push_back({x,z}); | |
| edge.push_back({{x,y},z}); | |
| } | |
| dick(0,adj1,dist1); | |
| dick(n - 1,adj2,dist2); | |
| ll ans = inf; | |
| ffor(i,m){ | |
| int x = edge[i].ff.ff; | |
| int y = edge[i].ff.ss; | |
| int z = edge[i].ss; | |
| ans = min(ans,dist1[x] + dist2[y] + z/2); | |
| } | |
| cout << ans; | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment