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