AtCoder Beginner Contest 061
Updated:
Source codes
Solutions
A - Between Two Integers
Determine if $A \leq C \land C \leq B$.
B - Counting Roads
Do as they indicate us to.
C - Big Array
Possess the integers by vector<int> V(100010, 0);. Then binary search works.
D - Score Attack
Assume $0$-indexed. We possess the paths by vector<Edge> V; where Edge is a struct which has the source $a$, the destination $b$ and the cost $-c$. The shortest path is determined by Bellman–Ford’s algorithm. Note that the shortest path consists at most $N - 1$ edges.
vector<ll> D(N, infty);
D[0] = 0;
for (auto k = 0; k < N - 1; ++k)
{
for (auto i = 0; i < M; ++i)
{
ch_min(D[E[i].dst], D[E[i].src] + E[i].cost);
}
}
What we should do is to separate the shortest path part and the loop determination part. How can we determine the negative loop? In this problem, if both of the followings are satisfied, the answer is inf.
- There exists a negative loop connected from $0$.
- One of those are connected to $N - 1$.
We create vector<bool> update(N, false); and will update it.
For 1., we just execute the update once more. For 2., we execute $N - 1$ times more, too. If the condition 2. holds, updated[N - 1] will become true since the loop consists of at most $N$ edges. This enable us to distinguish inf and $D[N - 1]$.