Fine Dining

#include <bits/stdc++.h>
using namespace std;
 
struct Pasture {
	int cost;
	int index;
	bool had_hay;
 
	bool operator<(const Pasture &other) const {
		return cost > other.cost;  // For priority queue
	}
};
 
int main() {
	freopen("dining.in", "r", stdin);
	freopen("dining.out", "w", stdout);
 
	int n, m, k;
	cin >> n >> m >> k;
	vector<vector<pair<int, int>>> adj(n);
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[--u].push_back({--v, w});
		adj[v].push_back({u, w});
	}
 
	vector<int> hay(n);
	for (int i = 0; i < k; i++) {
		int index, yumminess;
		cin >> index >> yumminess;
		index--;
		hay[index] = max(hay[index], yumminess);
	}
 
	priority_queue<Pasture> pq;
 
	/*
	 * dist[i][0] = shortest path from cow i to barn without stopping for haybales
	 * dist[i][1] = shortest path from cow i to barn with stopping for a haybale
	 */
	vector<array<int, 2>> dist(n, {INT_MAX, INT_MAX});
 
	dist[n - 1][0] = 0;  // Distance to barn without hay
	pq.push({0, n - 1, false});
 
	if (hay[n - 1] > 0) {
		dist[n - 1][1] = 0;
		pq.push({-hay[n - 1], n - 1, true});
	}
 
	while (!pq.empty()) {
		auto pasture = pq.top();
		pq.pop();
 
		int cost = pasture.cost;
		int index = pasture.index;
		bool had_hay = pasture.had_hay;
 
		if (dist[index][had_hay] < cost) continue;
 
		for (auto &[next, w] : adj[index]) {
			int new_cost = cost + w;
 
			if (had_hay) {
				if (dist[next][1] > new_cost) {
					dist[next][1] = new_cost;
					pq.push({new_cost, next, true});
				}
			} else {
				if (dist[next][0] > new_cost) {
					dist[next][0] = new_cost;
					pq.push({new_cost, next, false});
				}
 
				if (hay[next] > 0 && dist[next][1] > new_cost - hay[next]) {
					dist[next][1] = new_cost - hay[next];
					pq.push({new_cost - hay[next], next, true});
				}
			}
		}
	}
 
	for (int i = 0; i < n - 1; i++) {
		if (dist[i][1] <= dist[i][0]) {
			cout << 1 << '\n';
		} else {
			cout << 0 << '\n';
		}
	}
}

import java.io.*;
import java.util.*;
 
public class FineDining {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(new File("dining.in"));
		PrintWriter out = new PrintWriter("dining.out");
 
		int n = sc.nextInt();
		int m = sc.nextInt();
		int k = sc.nextInt();
		List<List<Edge>> adj = new ArrayList<>();
		for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			int time = sc.nextInt();
			adj.get(a).add(new Edge(b, time));
			adj.get(b).add(new Edge(a, time));
		}
		int[] haybales = new int[n];
		Arrays.fill(haybales, -1);
		for (int i = 0; i < k; i++) { haybales[sc.nextInt() - 1] = sc.nextInt(); }
 
		/*
		 * dist[i][0] - the shortest distance from cow i to the barn given
		 * that it doesn't eat any haybales.
		 *
		 * dist[i][1] - the shortest distance given that it eats one haybale.
		 * This distance is subtracted by the yuminess of the haybale the cow
		 * eats.
		 */
		int[][] dist = new int[n][2];
		for (int i = 0; i < n; i++) {
			dist[i][0] = -1;
			dist[i][1] = -1;
		}
 
		// run djiskstra's to find the shortest distances
		PriorityQueue<State> pq = new PriorityQueue<>();
		pq.add(new State(n - 1, 0, 0));
		while (!pq.isEmpty()) {
			State state = pq.remove();
			if (dist[state.pos][state.eaten] != -1) { continue; }
			dist[state.pos][state.eaten] = state.time;
 
			// add all the neighbors
			for (Edge e : adj.get(state.pos)) {
				pq.add(new State(e.other, state.time + e.time, state.eaten));
			}
 
			// if there's a haybale and the cow hasn't eaten any yet, eat the
			// haybale and update the state accordingly
			if (haybales[state.pos] != -1 && state.eaten == 0) {
				state.time -= haybales[state.pos];
				pq.add(new State(state.pos, state.time, 1));
			}
		}
 
		for (int i = 0; i < n - 1; i++) {
			// output 1 if it's better for cow to eat haybale along its path
			if (dist[i][1] <= dist[i][0]) {
				out.println(1);
			} else {
				out.println(0);
			}
		}
		out.close();
	}
 
	static class Edge {
		int other, time;
 
		Edge(int other, int time) {
			this.other = other;
			this.time = time;
		}
	}
 
	static class State implements Comparable<State> {
		int pos, time;
		int eaten;  // 1 if true, 0 if false
 
		State(int pos, int time, int eaten) {
			this.pos = pos;
			this.time = time;
			this.eaten = eaten;
		}
 
		@Override
		public int compareTo(State other) {
			// we have to prioritize cows that haven't eaten yet so that we
			// calculate all of dist[i][0] before calculating dist[i][1]
			if (this.eaten != other.eaten) { return this.eaten - other.eaten; }
			return this.time - other.time;
		}
	}
}