cppAcademy
FROM LEARNING TO COMPETING

Real problems.
Your next challenge.

Explore the Group C Olympiad archive.
Choose a topic. Find a challenge. Build your solution.

213 tasks across the Municipal, Regional, and National rounds (2009–2026), plus 4 previously featured problems. 146 tasks have independently written English summaries, analyses, and C++17 solutions; the remaining entries link to Arena. Topic tags are from Arena or our reviewed explanations. Difficulty labels are learning estimates, not official ratings.
GROUP C2015 · MediumDijkstra & weighted routes

Game

National Olympiad — Regional round

Submission name: game.cpp

Solve in Editor →

Problem summary

A player starts with K points and travels from intersection 1 to N. Each undirected street awards P points but takes T units of time. After the trip, total travel time is subtracted from the score. Maximize the final score.

Input

N M K; then M lines a b P T.

Output

The largest achievable final score.

Constraints

1 ≤ N ≤ 20,000; 1 ≤ M ≤ 200,000; 1 ≤ K ≤ 20,000; 1 ≤ P<T≤100.

Worked example

An independently prepared example for this explanation.

Input

3 3 10
1 2 2 4
2 3 4 5
1 3 1 8

Output

7

Solution analysis

  1. Each street changes the score by P−T, or equivalently loses T−P points.
  2. Replace its weight with the positive loss T−P.
  3. Run Dijkstra from 1 to minimize the total loss to N.
  4. The answer is K minus that minimum loss. A negative final score is still a numeric answer; there is no stated rule forbidding it.

Why it works

For every route, final score equals K minus the sum of edge losses. Maximizing that expression is exactly minimizing its loss. All losses are positive, so Dijkstra applies.

Complexity: O((N+M) log(N+M)) time with a lazy heap, O(N+M) space.

Watch out. The statement does not specify an unreachable-destination output. The code assumes the requested route exists and gives no invented sentinel otherwise.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<queue>
#include<functional>
#include<utility>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,k;
    cin>>n>>m>>k;
    vector<vector<pair<int,int>>>g(n+1);
    for(int i=0;i<m;++i){
        int a,b,p,t;
        cin>>a>>b>>p>>t;
        g[a].push_back({b,t-p});
        g[b].push_back({a,t-p});
    }
    const long long INF=(1LL<<60);
    vector<long long>d(n+1,INF);
    using State=pair<long long,int>;
    priority_queue<State,vector<State>,greater<State>>q;
    d[1]=0;
    q.push({0,1});
    while(!q.empty()){
        auto[dv,v]=q.top();
        q.pop();
        if(dv!=d[v]){
            continue;
        }
        for(auto[u,w]:g[v]){
            if(d[u]>dv+w){
                d[u]=dv+w;
                q.push({d[u],u});
            }
        }
    }
    if(d[n]==INF){
        return 0; // No unreachable output is defined in the PDF.
    }
    cout<<k-d[n]<<'\n';
}

Source: Arena Olimpiici ↗