Micemaze - why does my Java code work but not my C++ code?

[puckmcpuck]

Hello, I attempted to solve the problem Mice and Mazes (code MICEMAZE) and my Java code was accepted while my C++ code kept getting wrong answer (I used C++14, both gcc and clang). On my own test cases, the output appears identical. I tried to keep the two programs as similar as possible. Why isn’t my C++ code working?

Here is my C++ code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

typedef vector<vector<pair<int, int>>> AdjList;
typedef pair<int, int> Edge;

int minTime(AdjList adjList, int start, int end)
{
	vector<int> dist(adjList.size(), 1e9);
	dist.at(start) = 0;

	priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
	pq.emplace(0, start);

	while (!pq.empty())
	{
		Edge edge = pq.top();
		pq.pop();
		int w = edge.first;  // weight of edge
		int i = edge.second; // index of node

		// optimizations
		if (i == end) return dist.at(end);
		if (w > dist.at(i)) continue;

		// loop through connected nodes
		for (const auto &otherEdge : adjList.at(i))
		{
			int ow = otherEdge.first; // weight of edge
			int oi = otherEdge.second; // index of other node
			if (dist.at(i) + ow < dist.at(oi))
			{
				dist.at(oi) = dist.at(i) + ow;
				pq.emplace(dist.at(oi), oi);
			}
		}
	}

	return dist.at(end);
}

int main()
{
	/***  Input  ***/

	int n, e, t, m;
	cin >> n >> e >> t >> m;
	e--;

	// dist, id
	AdjList adjList(n);
	for (int i = 0; i < m; ++i)
	{
		int a, b, d;
		cin >> a >> b >> d;
		adjList.at(a - 1).emplace_back(d, b - 1);
	}

	/***  Processing  ***/
	int numMice = 0;
	for (int i = 0; i < n; ++i)
	{
		int time = minTime(adjList, i, e);
		if (time <= t)
		{
			numMice++;
		}
	}

	/***  Output  ***/
	cout << numMice << endl;
}

Here is my Java code:

import java.io.*;
import java.util.*;

public class Main
{
	public static void main(String[] args) throws IOException
	{
		/* Input */
		Scanner in = new Scanner(System.in);

		int n, e, t, m;
		n = in.nextInt();
		e = in.nextInt();
		t = in.nextInt();
		m = in.nextInt();
		e--;

		List<List<Edge>> adjList = new ArrayList<>();
		for (int i = 0; i < n; i++)
		{
			adjList.add(new ArrayList<>());
		}
		for (int i = 0; i < m; i++)
		{
			int a, b, d;
			a = in.nextInt();
			b = in.nextInt();
			d = in.nextInt();
			adjList.get(a-1).add(new Edge(d, b-1));
		}

		in.close();

		/* Processing */
		int numMice = 0;
		for (int i = 0; i < n; i++)
		{
			int time = minTime(adjList, i, e);
			if (time <= t)
				numMice++;
		}

		/* Output */
		System.out.println(numMice);

	}

	private static int minTime(List<List<Edge>> adjList, int start, int end)
	{
		List<Integer> dist = new ArrayList<>(adjList.size());
		for (int i = 0; i < adjList.size(); i++)
		{
			dist.add((int) 1e9);
		}
		dist.set(start, 0);

		PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt((Edge a) -> a.dist));
		pq.add(new Edge(0, start));

		while (!pq.isEmpty())
		{
			Edge edge = pq.poll();
			int w = edge.dist;
			int i = edge.id;

			// optimizations
			if (i == end) return dist.get(end);
			if (w > dist.get(i)) continue;

			// loop through connected nodes
			for (Edge otherEdge : adjList.get(i))
			{
				int ow = otherEdge.dist;
				int oi = otherEdge.id;
				if (dist.get(i) + ow < dist.get(oi))
				{
					dist.set(oi, dist.get(i) + ow);
					pq.add(new Edge(dist.get(oi), oi));
				}
			}
		}

		return dist.get(end);
	}

	static class Edge
	{
		int dist;
		int id;

		public Edge(int dist, int id)
		{
			this.dist = dist;
			this.id = id;
		}
	}
}

[vector9x]

Your C++ code is producing Accepted for me. However, some observations on your code:

• In function minTIme, the graph could be passed as a reference, to avoid copying.
• The “optimizations” part seems buggy. It should probably do the w > dist.at(i) verification before the i==end one.

For the java one:

• Using new Scanner(new BufferedReader(new InputStreamReader(System.in))) can improve time spent in IO by a lot.
• Primitive arrays can have size assigned at runtime. E.g. you can use int dist[] = new int[adjList.size()], instead of ArrayList<Integer>.
• Your version is not exactly equivalent to the C++ one. C++ pairs are compared by both fields; your java comparator is comparing only by dist.

About the approach:

• You could try to solve this problem by running Dijkstra only once: from the exit to all the mice

[puckmcpuck]

Thank you for the feedback! I found out that I made changes to the C++ code that I forgot to upload to the judge before posting here (in the pq.emplace line, I had been using pq.push(otherEdge) for some reason). I will make sure to improve my code based on your observations .