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


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';
}
}