Proficient.
Put your skills to the test.

Problem summary

Find a directed walk from1 toN using at most2M edges, minimizing the sum of signed edge costs. On every visit to a selling country receive one vignette; at mostN may be held. Spending one makes the next edge cost0. Output an optimal walk and which edges are paid normally.

Constraints

N≤80;M≤500;1≤|cost|≤100000; edges have distinct endpoints; a feasible journey exists; at most2M traversals.

Worked example

Independently prepared teaching example; any optimal valid route is accepted.

3 3
1 0 0
1 2 5
2 3 -2
1 3 7

-2 2
1 0
2 1

Solution analysis

1. Negative costs and revisits rule out ordinary Dijkstra. The explicit2M-edge limit supplies an acyclic DP dimension: dp[length][country][tickets] is the smallest cost after exactly that many crossings and collecting the arrival-country ticket. Initialize country1 with its selling flag.
2. From each reachable state and outgoing edge, either pay its signed cost or, if a ticket is available, spend it and pay0. Then collect the destination ticket and reject states with more thanN tickets. Keep separate current and next layers, so one iteration represents exactly one crossing.
3. Store the chosen edge and payment bit for each improved state. Its predecessor country is the edge source, and its predecessor ticket count is currentTickets−seller[destination]+(spent?1:0); no full predecessor-state object is needed. Select the cheapest terminal state over all lengths, including0 whenN=1. In the teaching example, spend the initial ticket on cost5 and retain the negative cost−2, yielding−2.

Why it works

Inductively the transitions enumerate every legal choice for every walk of a fixed length, with exactly its ticket balance and cost. Taking minima therefore computes the optimum for that length/state. Minimizing over terminal states with length≤2M covers exactly all permitted walks. Stored predecessor choices reconstruct a walk realizing the chosen minimum.

Watch out. A voucher should usually not cancel a negative edge, but the DP safely considers both choices. Updates must not reuse the current length layer. Collect tickets on the starting visit and every arrival. Stop is optional after reachingN: a later bounded negative-cost detour may improve the answer.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<limits>
#include<utility>
#include<vector>
using namespace std;
struct Edge{
    int from;
    int to;
    int cost;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<int>seller(n+1);
    for(int i=1;i<=n;i++){
        cin>>seller[i];
    }
    vector<Edge>edges(m+1);
    for(int i=1;i<=m;i++){
        cin>>edges[i].from>>edges[i].to>>edges[i].cost;
    }
    int width=n+1;
    int states=n*width;
    int maxLength=2*m;
    const long long infinity=numeric_limits<long long>::max()/4;
    vector<long long>current(states,infinity),next(states,infinity);
    vector<unsigned short>choice(static_cast<size_t>(maxLength+1)*states,0);
    auto state=[&](int vertex,int tickets){
        return (vertex-1)*width+tickets;
    };
    current[state(1,seller[1])]=0;
    long long best=n==1?0:infinity;
    int bestLength=0;
    int bestTickets=seller[1];
    for(int length=1;length<=maxLength;length++){
        fill(next.begin(),next.end(),infinity);
        for(int id=1;id<=m;id++){
            const Edge&edge=edges[id];
            for(int tickets=0;tickets<=n;tickets++){
                long long base=current[state(edge.from,tickets)];
                if(base==infinity){
                    continue;
                }
                for(int paid=0;paid<=1;paid++){
                    if(paid==0&&tickets==0){
                        continue;
                    }
                    int remaining=tickets-(paid==0)+seller[edge.to];
                    if(remaining>n){
                        continue;
                    }
                    int destination=state(edge.to,remaining);
                    long long candidate=base+(paid?edge.cost:0);
                    if(candidate<next[destination]){
                        next[destination]=candidate;
                        // Record the decision; the previous ticket count is reversible.
                        choice[static_cast<size_t>(length)*states+destination]=
                            static_cast<unsigned short>(2*id+paid);
                    }
                }
            }
        }
        current.swap(next);
        for(int tickets=0;tickets<=n;tickets++){
            if(current[state(n,tickets)]<best){
                best=current[state(n,tickets)];
                bestLength=length;
                bestTickets=tickets;
            }
        }
    }
    vector<pair<int,int>>route;
    int vertex=n;
    int tickets=bestTickets;
    for(int length=bestLength;length>0;length--){
        int decision=choice[static_cast<size_t>(length)*states+state(vertex,tickets)];
        int id=decision/2;
        int paid=decision%2;
        route.push_back({id,paid});
        tickets=tickets-seller[vertex]+(paid==0);
        vertex=edges[id].from;
    }
    reverse(route.begin(),route.end());
    cout<<best<<' '<<route.size()<<'\n';
    for(auto[id,paid]:route){
        cout<<id<<' '<<paid<<'\n';
    }
}