verify/aizu/aizu-GRL_1_A.test.cpp

View this file on GitHub
Last update: 2022-07-21 16:12:33-04:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/graphs/dijkstra.hpp"

int main() {
	using namespace std;
	cin.tie(0)->sync_with_stdio(0);
	int n, m, r;
	cin >> n >> m >> r;
	Dijkstra<long long, true> D;
	D.init(n);
	while (m--) {
		int u, v, w;
		cin >> u >> v >> w;
		D.ae(u, v, w);
	}
	D.gen(r);
	for (int i = 0; i < n; ++i) {
		auto dist = D.dist[i];
		if (dist == numeric_limits<long long>::max()) {
			cout << "INF" << '\n';
		} else {
			cout << dist << '\n';
		}
	}
}

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A"


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

template <class C, bool directed> struct Dijkstra {
	int SZ; std::vector<C> dist;
	std::vector<std::vector<std::pair<int, C>>> adj;

	void init(int _SZ) {
		SZ = _SZ;
		adj.clear();
		adj.resize(SZ);
	}

	void ae(int u, int v, C cost) {
		adj[u].emplace_back(v, cost);
		if (!directed) adj[v].emplace_back(u, cost);
	}

	void gen(int st) {
		dist = std::vector<C>(SZ, std::numeric_limits<C>::max());
		typedef std::pair<C, int> T;
		std::priority_queue<T, std::vector<T>, std::greater<T>> pq;
		auto ad = [&](int a, C b) {
			if (dist[a] <= b) return;
			pq.push({dist[a] = b, a});
		};
		ad(st, 0);
		while (!pq.empty()) {
			auto x = pq.top();
			pq.pop();
			if (dist[x.second] < x.first) continue;
			for (auto& y: adj[x.second]) {
				ad(y.first, x.first + y.second);
			}
		}
	}
};

int main() {
	using namespace std;
	cin.tie(0)->sync_with_stdio(0);
	int n, m, r;
	cin >> n >> m >> r;
	Dijkstra<long long, true> D;
	D.init(n);
	while (m--) {
		int u, v, w;
		cin >> u >> v >> w;
		D.ae(u, v, w);
	}
	D.gen(r);
	for (int i = 0; i < n; ++i) {
		auto dist = D.dist[i];
		if (dist == numeric_limits<long long>::max()) {
			cout << "INF" << '\n';
		} else {
			cout << dist << '\n';
		}
	}
}