Atcoder Weekday Contest 058

ll n,p,t,c,res;
 
auto solve = [](){
    ri(n, p, t, c);
    vl v(n); ri(v);
    sort(rall(v));
    for(int i = 0; i < n; i++){
        if(p >= t) break;
        p = v[i];
        res += c;
    }
    po(p >= t ? res : -1);
};

ll n,m,k,res;
ll v[1 << 20];
 
auto solve = [](){
    ri(n, m, k);
    for(int i = 1; i <= n; i++){
        ri(v[i]);
        v[i] = (v[i] >= k ? v[i] : 0);
    }
    for(int i = 1; i <= n; i++) v[i] += v[i - 1];
    ll mx = 0;
    for(int i = 1; i + m - 1 <= n; i++){
        int l = i, r = i + m - 1;
        mx = max(mx, v[r] - v[l - 1]);
        //debug(l, r);
    }
    po(mx);
};

ll n,m,k,res;
ll v[1 << 20];
 
auto solve = [](){
    ri(n, m, k);
    while (m--){
        ll a,b; ri(a, b);
        v[a]++, v[b + 1]--;
    }
    for(int i = 1; i <= n + 1; i++) v[i] += v[i - 1];
    for(int i = 1; i <= n; i++) res += (v[i] >= k);
    po(res); 
};

ll n,m,k;
vector<pll> g[1 << 18];
 
vector<ll> dijkstra(ll st){
    vector<ll> dist(n + 1, iinf);
    minpq<pll> pq;
    pq.push({dist[st] = 0, st});
    while(si(pq)){
        auto [cdist, cur] = pq.top(); pq.pop();
        if(dist[cur] < cdist) continue;
        for(const auto& [cost, nxt] : g[cur]){
            if(dist[nxt] > cdist + cost){
                pq.push({dist[nxt] = cdist + cost, nxt});
            }
        }
    }
    return dist;
}
 
auto solve = [](){
    ri(n, m, k);
    while(m--){
        ll a,b,c; ri(a, b, c);
        g[a].pb({c, b}); g[b].pb({c, a});
    }
    auto dist1 = dijkstra(1);
    auto dist2 = dijkstra(k);
    if(dist1[k] == iinf or dist2[n] == iinf) po(-1);
    else po(dist1[k] + dist2[n]);
};