https://toph.co/p/ada-in-dreamland

Ada in Dreamland.cc

#include <bits/stdc++.h>

using namespace std;

typedef double T;

const int N = 1e3 + 7;
const T INF = 1e18;

vector<int> g[N];
vector<T> c[N];
T dis[N];
bool vis[N];

vector<int> bellmanford(int n, int src = 1) {
	for(int i=1; i<=n; ++i) {
		dis[i] = INF;
	}
	dis[src] = 0;

	vector<int> ret;
	for(int i=1; i<=n; ++i) {
		for(int u=1; u<=n; ++u) {
			for(int j=0; j<(int) g[u].size(); ++j) {
				int v = g[u][j];
				T w = c[u][j];
				if(dis[v] > dis[u] + w) {
					dis[v] = dis[u] + w;
					if(i == n) {
						ret.push_back(u);
						break;
					}
				}
			}
		}
	}

	return ret;
}

void dfs(int u) {
	vis[u] = true;
	for(int v : g[u]) if(!vis[v]) dfs(v);
}

const int NODE_MAX = 1e3;
const int EDGE_MAX = 1e5;
const T WEIGHT_MAX = 1e6;

int main() {
	clock_t clk = clock();

	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, m;
	T d;
	assert(cin >> n >> m >> d);

	assert(n >= 2 and n <= NODE_MAX);
	assert(m >= 0 and m <= min(n*(n-1), EDGE_MAX));
	assert(d > 0 and d <= WEIGHT_MAX);

	while(m--) {
		int u, v;
		T w;
		assert(cin >> u >> v >> w);

		assert(u >= 1 and u <= n);
		assert(v >= 1 and v <= n);
		assert(w > 0 and w <= WEIGHT_MAX);

		w = log(w);
		g[u].push_back(v);
		c[u].push_back(w);
	}

	string str;
	assert(!(cin >> str));

	memset(vis, false, sizeof vis);
	dfs(1);
	if(!vis[n]) {
		cout << "Unreachable\n";
		cerr << "Time elapsed: " << fixed << (double) (clock() - clk) / CLOCKS_PER_SEC << " | Unreachable" << "\n";
		return 0;
	}

	auto vec = bellmanford(n, 1);
	memset(vis, false, sizeof vis);
	for(int v : vec) if(!vis[v]) dfs(v);

	if(vis[n]) {
		cout << "Yes\n";
		cerr << "Time elapsed: " << fixed << (double) (clock() - clk) / CLOCKS_PER_SEC << " | Yes" << "\n";
	}
	else {
		cout << "No\n";
		cerr << "Time elapsed: " << fixed << (double) (clock() - clk) / CLOCKS_PER_SEC << " | No" << "\n";
	}

	return 0;
}