#include <iostream>
#include <queue>
#include <vector>
#include <limits.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pll;
int main(){
cin.tie(0);
cout.sync_with_stdio(false);
ll N, M;
cin >> N >> M;
vector<vector<pll> > adj_list;
adj_list.resize(N);
for (ll i = 0; i < M; i++){
ll a, b, w;
cin >> a >> b >> w;
a--; b--;
adj_list[a].push_back({b, w});
adj_list[b].push_back({a, w});
}
vector<ll> dist;
dist.resize(N, LLONG_MAX);
dist[0] = 0;
// Dijkstra's algo
priority_queue<pll, vector<pll>, greater<pll>> pq;
pq.push({0, 0});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // stale entry
for (auto [v, w] : adj_list[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
if (dist[N - 1] == LLONG_MAX){
cout << -1;
} else {
cout << dist[N-1];
}
return 0;
}#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pll;
vector<vector<pll> > adj_list;
vector<vector<ll> > dist;
ll N;
#define INF 1000000001
void floyd() {
for (int i = 0; i < N; i++) {
for (auto neighbour: adj_list[i]){
dist[i][neighbour.first] = neighbour.second; // adj list is i -> neighbour, dist[from][to]
}
dist[i][i] = 0;
}
for (int mid = 0; mid < N; mid++) {
for (int u = 0; u < N; u++) {
for (int v = 0; v < N; v++) {
if (dist[u][mid] + dist[mid][v] < dist[u][v]) { // update edge
dist[u][v] = dist[u][mid] + dist[mid][v];
}
}
}
}
}
int main(){
cin.tie(0);
cout.sync_with_stdio(false);
ll M, Q;
cin >> N >> M >> Q;
adj_list.resize(N);
for (ll i = 0; i < M; i++){
ll a, b, w;
cin >> a >> b >> w;
adj_list[a].push_back({b, w});
adj_list[b].push_back({a, w});
}
dist.resize(N);
for (ll i = 0; i<N; i++){
dist[i].resize(N, INF);
}
floyd();
for (ll i = 0; i<Q; i++){
ll a, b;
cin >> a >> b;
if (dist[a][b] == INF){
cout << -1 << '\n';
} else {
cout << dist[a][b] << '\n';
}
}
return 0;
}#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
ll deepest = 0;
vector<vector<ll> > adj; // Adj list where nodes[i] -> subordinates of i
vector<bool> visited;
void dfs(ll node, ll depth) {
deepest = max(depth, deepest);
visited[node] = true;
for (auto neighbour: adj[node]){
if (!visited[neighbour]) {
dfs(neighbour, depth + 1);
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// ================ TAKE INPUT
ll N, E;
cin >> N;
adj.resize(N);
visited.resize(N, false);
for (ll i = 1; i <= N-1; i++) {
ll boss_of_i;
cin >> boss_of_i;
adj[boss_of_i].push_back(i);
}
dfs(0, 1); // 0 is the root.
cout << deepest;
return 0;
}#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> coord_t;
#define X .first
#define Y .second
struct pair_hash{
template <class T1, class T2>
std::size_t operator() (const std::pair<T1, T2> &pair) const {
return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
}
};
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// Taking input
ll board_size;
cin >> board_size;
coord_t init;
cin >> init X >> init Y;
coord_t target;
cin >> target X >> target Y;
ll forbid_n;
cin >> forbid_n;
unordered_set<coord_t, pair_hash> forbids;
for (ll i = 0; i<forbid_n; i++){
coord_t forbid;
cin >> forbid X >> forbid Y;
forbids.insert(forbid);
}
// Legal moves
#define MOVES 8
vector<ll> dx = {-1, +1, -1, +1, -2, -2, +2, +2};
vector<ll> dy = {-2, -2, +2, +2, -1, +1, -1, +1};
// BFS init.
unordered_set<coord_t, pair_hash> visited; // if it is in this, it is visited already.
queue< pair<coord_t, ll> > to_explore; // {to explore, moves made to get there};
// BIG ASSUMPTION: initial is not among forbidden.
if (init == target){
cout << 0;
return 0;
}
visited.insert({0, 0});
to_explore.push({init, 0});
while (!to_explore.empty()){
auto [exploring, moves_to_here] = to_explore.front();
ll moves_to_visiting = moves_to_here + 1;
to_explore.pop();
for (ll i = 0; i < MOVES; i++){
coord_t visiting = {exploring X + dx[i], exploring Y + dy[i]};
// Do not visit if out of board or visited or forbidden.
if (visiting X < 0 or visiting X > board_size or
visiting Y < 0 or visiting Y > board_size or
visited.find(visiting) != visited.end() or
forbids.find(visiting) != forbids.end()){
continue;
}
// Visit
if (visiting == target){
cout << moves_to_visiting;
return 0;
}
visited.insert(visiting);
// Mark to explore.
to_explore.push({visiting, moves_to_visiting});
}
}
// if it got here, bfs terminated after doing all possibilities
cout << -1;
return 0;
}#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
// use & so that its pass-by-reference
vector<ll> dijkstra(vector< vector<pll> >& adj, ll source){
ll N = adj.size();
vector<ll> dist;
dist.resize(N, LLONG_MAX);
dist[source] = 0;
priority_queue<pll, vector<pll>, greater<pll>> pq;
pq.push({0, source}); // (distance, node)
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // stale entry
for (auto [v, w] : adj[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll nodes_n, edges_n;
cin >> nodes_n >> edges_n;
vector< vector<pll> > adj;
adj.resize(nodes_n);
for (ll i = 0; i<edges_n; i++){
ll a, b, f;
cin >> a >> b >> f;
adj[a].push_back({b, f});
adj[b].push_back({a, f});
}
vector<ll> dist_start = dijkstra(adj, 0);
vector<ll> dist_end = dijkstra(adj, nodes_n - 1);
ll original_best = dist_start[nodes_n - 1];
ll queries_n;
cin >> queries_n;
for (ll q = 0; q<queries_n; q++){
ll a, b;
cin >> a >> b;
// We need to find the shortest path which passes through AB
// Then, we get the cost of the path excluding AB.
ll constant_cost = LLONG_MAX;
if (dist_start[a] != LLONG_MAX && dist_end[b] != LLONG_MAX){
constant_cost = min(constant_cost, dist_start[a] + dist_end[b]);
}
if (dist_start[b] != LLONG_MAX && dist_end[a] != LLONG_MAX){
constant_cost = min(constant_cost, dist_start[b] + dist_end[a]);
}
if (constant_cost == LLONG_MAX){
// If this is the case, there exists no path from start to end which passes thru AB.
cout << -1 << '\n';
continue;
}
// non-negative ERP fee (≥ $0)
ll lower_bound = constant_cost; // (fee = 0)
if (lower_bound >= original_best){ // ie. cannot be improved
cout << -1 << '\n';
continue;
}
// Can be improved
cout << original_best - constant_cost - 1 << '\n';
}
return 0;
}#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> coord_t;
#define R .first
#define C .second
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// Taking input
ll rows, cols;
cin >> rows >> cols;
ll cells_n;
cin >> cells_n;
// BFS init.
#define visited_1idx(row, col) visited[(row)-1][(col)-1]
vector< vector<bool> > visited; // if visited[row][cols], visited alr.
visited.resize(rows);
for (ll i = 0; i<rows; i++){
visited[i].resize(cols, false);
}
queue< pair<coord_t, ll> > to_explore; // {to explore, number of shades used so far};
// BFS init end
// Counter
ll answer = 0;
for (ll i = 0; i<cells_n; i++){
coord_t seed;
cin >> seed R >> seed C;
to_explore.push({seed, 1});
// Visit seed
visited_1idx(seed R, seed C) = true; // REMEMBER TS OMG
answer = max(answer, 1LL);
}
// Legal moves
#define MOVES 8
vector<ll> dr = {-1, -1, -1, 0, 0, +1, +1, +1};
vector<ll> dc = {-1, 0, +1, -1, +1, -1, 0, +1};
// BFS
while (!to_explore.empty()){
auto [exploring, shades_so_far] = to_explore.front();
ll shades_at_visiting = shades_so_far + 1;
to_explore.pop();
for (ll i = 0; i < MOVES; i++){
coord_t visiting = {exploring R + dr[i], exploring C + dc[i]};
// Do not visit if out of board or visited
if (visiting R <= 0 or visiting R > rows or
visiting C <= 0 or visiting C > cols or
visited_1idx(visiting R,visiting C)){
continue;
}
// Visit
visited_1idx(visiting R, visiting C) = true;
answer = max(answer, shades_at_visiting);
// Mark to explore.
to_explore.push({visiting, shades_at_visiting});
}
}
// if it got here, bfs terminated after doing all possibilities
cout << answer;
return 0;
}