# HackerEarth Vertices and edges problem solution

In this HackerEarth Vertices and edges problem solution, You are given an undirected weighted graph with n vertices and m edges.

Consider all shortest paths between vertices 1 and n, for any vertex such as v(1 <= v <= n), says that, if v is in either all shortest paths or some of them or none of them.

## HackerEarth Vertices and edges problem solution.

`#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<ll, int> ii;const int N = 2e5+100, M = 3e5+10;const ll INF = 1e18;ll dis[N];int T, stt[N], who[N], cnt[N];vector<ii> g[N], d_es;vector<int> d[N], r[N];bool ok[N], mark[N], all[N];struct ed{  int v, u, w;  ed():    v(-1), u(-1), w(-1) {}  ed(int v, int u, int w):    v(v), u(u), w(w) {}} e[M];void dfs(int v){  ok[v] = true;  for(auto u : r[v])    if(!ok[u])      dfs(u);}void dfs_top(int v){  mark[v] = true;  for(auto u : d[v])    if(!mark[u] && ok[u])      dfs_top(u);  stt[v] = T++;  who[ stt[v] ] = v;}signed main(){  ios_base::sync_with_stdio(false);cin.tie(NULL);  int n, m;cin >> n >> m;  for(int i=0 ; i<m ; i++){    int v, u, w;cin >> v >> u >> w;v --;u --;    e[i] = ed(v, u, w);    g[v].push_back(ii(u, w));    g[u].push_back(ii(v, w));  }  for(int i=0 ; i<n ; i++)    dis[i] = INF;  set<ii> st;  st.insert(ii(0, 0));  dis[0] = 0;  while(!st.empty()){    int v = st.begin()->second;    st.erase(st.begin());    for(auto U : g[v]){      int u = U.first, w = U.second;      if(dis[u] > dis[v] + w){        st.erase(ii(dis[u], u));        dis[u] = dis[v] + w;        st.insert(ii(dis[u], u));      }    }  }  for(int i=0 ; i<m ; i++){    int v = e[i].v, u = e[i].u, w = e[i].w;    if(dis[v] > dis[u])      swap(v, u);    if(dis[v] + w == dis[u]){      d[v].push_back(u);      r[u].push_back(v);      d_es.push_back(ii(u, v));    }  }  dfs(n-1);  dfs_top(0);  for(auto e : d_es){    int v = e.first, u = e.second;    if(!ok[v] || !ok[u])      continue;    cnt[ stt[v]+1 ] ++;    cnt[ stt[u] ] --;  }  int sum=0;  for(int i=0 ; i<T ; i++){    sum += cnt[i];    if(!sum)      all[ who[i] ] = true;  }  int cnt1=0, cnt2=0;  for(int i=0 ; i<n ; i++){    if(!ok[i]){      cout << "none\n";      continue;    }    if(all[i]){      cnt2 ++;      cout << "all\n";    }else{      cnt1 ++;      cout << "some\n";    }  }  // assert(cnt1<100);  // assert(cnt2<100   );}`

### Second solution

`#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 2e5 + 14;const ll inf = 1e18;vector<pair<int, int> > g[maxn];set<pair<ll, int> > pq;bool need[maxn];int n, m;ll d[2][maxn];void dij(int source, ll d[]) {    fill(d, d + n, inf);    d[source] = 0;    pq.insert({0, source});    while (pq.size()) {        int v = pq.begin()->second;        pq.erase(pq.begin());        for (auto e : g[v])            if (d[e.first] > d[v] + e.second) {                pq.erase({d[e.first], e.first});                pq.insert({d[e.first] = d[v] + e.second, e.first});            }    }}int main() {    ios::sync_with_stdio(0), cin.tie(0);    cin >> n >> m;    for (int i = 0; i < m; ++i) {        int v, u, w;        cin >> v >> u >> w;        v--, u--;        g[v].emplace_back(u, w);        g[u].emplace_back(v, w);    }    dij(0, d[0]);    dij(n - 1, d[1]);    pq.insert({0, 0});    while (!pq.empty()) {        int v = pq.begin()->second;        pq.erase(pq.begin());        need[v] = pq.empty();        for (auto e : g[v])            if (d[0][v] + e.second + d[1][e.first] == d[0][n - 1]) {                pq.insert({d[0][e.first], e.first});            }    }    for (int i = 0; i < n; ++i) {        cout << (need[i] ? "all" : d[0][i] + d[1][i] == d[0][n - 1] ? "some" : "none") << '\n';    }}`