Submission #658386

#	Time	Username	Problem	Language	Result	Execution time	Memory
658386		TheEpicCowOfLife	Robot (JOI21_ho_t4)	C++14	100 / 100	919 ms	91720 KiB

Main

#include <bits/stdc++.h>

// #ifdef DEBUG
// #define D(..) = printf(..)
// #else
// #define D(..) = printf(..)
// #endif
using namespace std;

int n,m;
typedef long long ll;
typedef pair<ll, ll> pll;

// price, target
map<int,vector<pll>> g[100005];

map<int,ll> tc[100005];

/// final graph to dijkstra over
vector<pll> fg[100005];


// Observations: You want to reach each node at most once
// You can always assign a new unique edge 
// At each node you have two choices: Assign every other edge, and take the edge for free,
// or just assign

inline void add_edge(int u, int v, int c, long long p){
    if (g[u].find(c) == g[u].end()){
        vector<pll> vec;
        vec.push_back({p,v});
        g[u][c] = vec;
        tc[u][c] = p;
    }
    else{
        g[u][c].push_back({p,v});
        tc[u][c] += p;
    }
}
inline void add_change_edge(int u, int v, int c, long long p){
    // Add edge from u -> v
    fg[u].push_back({v,p});
    // printf("Added change base %d-%lld %lld\n", u, v, p);
    // I'm pretty sure you only need to consider the top 2 weights, but the math seems ab it tight and 
    // idk if I have all the cases considered

    // ll maxw = g[u][c][0].first;
    for (int i = 0; i < min(2,(int) g[v][c].size()); i++){
        ll tgt = g[v][c][i].second;
        ll w = g[v][c][i].first;
        if (tgt == u){
            continue; // don't do a back-edge
        }
        // New edge: Go from u to v to tgt, where we change u -> v, and don't change v -> tgt
        fg[u].push_back({tgt, tc[v][c] - w});

        // printf("Added change case %d-%lld %lld\n", u, tgt, tc[v][c] - w);
    }
}

ll dist[100005];
bool explored[100005];

priority_queue<pll,vector<pll>,greater<pll>> q;

int main(){
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= m; i++){
        int u,v,c;
        long long p;        
        scanf("%d %d %d %lld", &u,&v,&c,&p);
        add_edge(u,v,c,p);
        add_edge(v,u,c,p);
    }

    for (int i = 1; i <= n; i++){
        dist[i] = 1e18;
        // sort the vecs
        for (auto cur : g[i]){
            int c = cur.first;
            sort(g[i][c].begin(),g[i][c].end(), greater<pll>());
        }
    }

    for (int i = 1; i <= n; i++){
        for (auto cur : g[i]){
            int c = cur.first;            
            for (auto thing : cur.second){
                ll v = thing.second;
                ll p = thing.first;
                add_change_edge(i,v,c,p);
                fg[i].push_back({v,tc[i][c] - p});
                // printf("%lld %lld %lld\n", i, v , p);
            }
        }              
    }

    // for (int i = 1; i <= n; i++){
    //     for (auto tgt : fg[i]){
    //     }
    // }

    dist[1] = 1;
    q.push({0,1});
    while (!q.empty()){
        auto cur = q.top();
        q.pop();
        long long d = cur.first;
        long long x = cur.second;
        if (explored[x]){
            continue;
        }
        explored[x] = true;
        for (auto tgt : fg[x]){
            ll tdist = tgt.second + d;
            if (!explored[tgt.first] && tdist < dist[tgt.first]){
                q.push({tdist,tgt.first});
                dist[tgt.first] = tdist;
            }
        }       
    }
    if (dist[n] > 9e17){
        printf("-1\n");
    }
    else{
        printf("%lld\n", dist[n]);
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%d %d %d %lld", &u,&v,&c,&p);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42