In this HackerEarth Space smugglers problem solution Nathan Reynolds is a famous smuggler and captain of a spaceship "Serenade". He was offered a potentially dangerous job on Ariel, one of the border planets of the star system. But to save all the "honest" earnings of the previous adventures, he decided to store them on one of the planets on the way to the border.
Star system is represented by n planets and m space tunnels between them. Space tunnel is one-way wormhole to travel from one planet to another, requiring an amount of gravitonium to perform the gravity jump. There may be several space tunnels between two planets, but no space tunnel leads to the same planet it starts from.
Your task as a first officer is to find the minimum amount of gravitonium to travel from the base planet to Ariel, visiting some other planet to store the earnings, and return back to base, picking up the earnings on the way back.
Note, that storing the earnings in a base planet or the planet, where the job is taking place, is not allowed. But it's allowed to visit Ariel with the earnings as long as you are not doing a job on this planet.
HackerEarth Space smugglers problem solution.
import java.io.*;
import java.util.*;
public class int_paths_ag {
private static final int BIG = 1_000_000_000;
class Pair implements Comparable<Pair> {
int id;
long d;
Pair(int u, long s) {
id = u;
d = s;
}
@Override
public int compareTo(Pair p) {
if (p.d == d)
return Integer.compare(id, p.id);
return Long.compare(d, p.d);
}
}
private long[] dijkstra(int start, List<Edge>[] edges) {
int n = edges.length;
TreeSet<Pair> set = new TreeSet<>();
Pair[] d = new Pair[n];
for (int i = 0; i < n; ++i) {
d[i] = new Pair(i, i != start ? BIG : 0);
set.add(d[i]);
}
for (; !set.isEmpty(); ) {
Pair p = set.pollFirst();
(edges[p.id]).stream().filter(e -> d[e.v].d > d[e.u].d + e.w).forEach(e -> {
set.remove(d[e.v]);
d[e.v].d = d[e.u].d + e.w;
set.add(d[e.v]);
});
}
long[] res = new long[n];
for (int i = 0; i < n; ++i)
res[i] = d[i].d;
return res;
}
private class Edge {
int u, v, w;
Edge(int x, int y, int z) {
u = x;
v = y;
w = z;
}
}
private void solve() {
int n = rw.nextInt();
int m = rw.nextInt();
int start = rw.nextInt() - 1;
int end = rw.nextInt() - 1;
List<Edge>[] edges = new ArrayList[n];
List<Edge>[] revEdges = new ArrayList[n];
for (int i = 0; i < n; ++i) {
edges[i] = new ArrayList<>();
revEdges[i] = new ArrayList<>();
}
for (int i = 0; i < m; ++i) {
int u = rw.nextInt() - 1;
int v = rw.nextInt() - 1;
int w = rw.nextInt();
edges[u].add(new Edge(u, v, w));
revEdges[v].add(new Edge(v, u, w));
}
long[] d1 = dijkstra(start, edges);
long[] d2 = dijkstra(end, revEdges);
long[] d3 = dijkstra(end, edges);
long[] d4 = dijkstra(start, revEdges);
long ans = Long.MAX_VALUE;
for (int i = 0; i < n; ++i)
if (i != start && i != end)
if (d1[i] < BIG && d2[i] < BIG && d3[i] < BIG && d4[i] < BIG)
ans = Math.min(ans, d1[i] + d2[i] + d3[i] + d4[i]);
rw.println(ans == Long.MAX_VALUE ? -1 : ans);
}
private RW rw;
private String FILE_NAME = "file";
public static void main(String[] args) {
new int_paths_ag().run();
}
private void run() {
rw = new RW(FILE_NAME + ".in", FILE_NAME + ".out");
solve();
rw.close();
}
private class RW {
private StringTokenizer st;
private PrintWriter out;
private BufferedReader br;
private boolean eof;
RW(String inputFile, String outputFile) {
br = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(new OutputStreamWriter(System.out));
File f = new File(inputFile);
if (f.exists() && f.canRead()) {
try {
br = new BufferedReader(new FileReader(inputFile));
out = new PrintWriter(new FileWriter(outputFile));
} catch (IOException e) {
e.printStackTrace();
}
}
}
private String nextLine() {
String s = "";
try {
s = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return s;
}
private String next() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
eof = true;
return "-1";
}
}
return st.nextToken();
}
private long nextLong() {
return Long.parseLong(next());
}
private int nextInt() {
return Integer.parseInt(next());
}
private void println() {
out.println();
}
private void println(Object o) {
out.println(o);
}
private void print(Object o) {
out.print(o);
}
private void close() {
try {
br.close();
} catch (IOException e) {
e.printStackTrace();
}
out.close();
}
}
}Second solution
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <assert.h>
#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds
#define ends asdgahhfdsfshdshfd
#define eps 1e-8
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 512
#define ldouble long double
using namespace std;
long long INF = 1e9;
const int N = 210031;
vector<pair<int,int> > g[N],gr[N];
int n,m,s,t;
int dist1[N],dist2[N],dist3[N];
int d[N];
set<pair<int,int> > S;
set<pair<int,int> > ::iterator it;
int dist4[N];
vector<pair<int,int> > G[N];
void trace(int v,int flag)
{
for (int i=1;i<=n;i++)
{
G[i].clear();
}
for (int i=1;i<=n;i++)
{
if (flag==1)
{
for (int j=0;j<gr[i].size();j++)
{
G[i].push_back(gr[i][j]);
}
}
else
{
for (int j=0;j<g[i].size();j++)
{
G[i].push_back(g[i][j]);
}
}
}
for (int i=1;i<=n;i++)
{
d[i]=1e9;
}
d[v]=0;
for (int i=1;i<=n;i++)
{
S.insert(make_pair(d[i],i));
}
while (S.size())
{
it=S.begin();
pair<int,int>p=(*it);
S.erase(it);
int qv=p.second;
// cout<<p.first<<"^"<<p.second<<endl;
for (int i=0;i<G[qv].size();i++)
{
int to=G[qv][i].first;
int cost=d[qv]+G[qv][i].second;
if (d[to]>cost)
{
S.erase(make_pair(d[to],to));
d[to]=cost;
S.insert(make_pair(d[to],to));
}
}
}
}
int main(){
//freopen("tree.in","r",stdin);
//freopen("tree.out","w",stdout);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
ios_base::sync_with_stdio(0);
//cin.tie(0);
cin>>n>>m>>s>>t;
for (int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
g[a].push_back(make_pair(b,c));
gr[b].push_back(make_pair(a,c));
}
//cout<<"@"<<endl;
trace(s,0);
for (int i=1;i<=n;i++)
{
dist1[i]=d[i];
}
trace(t,1);
for (int i=1;i<=n;i++)
{
dist2[i]=d[i];
}
trace(t,0);
for (int i=1;i<=n;i++)
{
dist3[i]=d[i];
}
trace(s,1);
for (int i=1;i<=n;i++){
dist4[i]=d[i];
}
long long best=1e9;
for (int i=1;i<=n;i++){
if (i==s||i==t)
continue;
best=min(best,0ll+dist1[i]+dist2[i]+dist3[i]+dist4[i]);
}
if (best>5e8)
{
cout<<-1<<endl;
}
else
{
cout<<best<<endl;
}
cin.get(); cin.get();
return 0;
}
0 Comments