제출 #658375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
658375		TheEpicCowOfLife	Robot (JOI21_ho_t4)	C++14	24 / 100	881 ms	97864 KiB

Main

#include <bits/stdc++.h>

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];


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});

    // 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(10,(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});
    }
}

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]){
            sort(cur.second.begin(),cur.second.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);
                if (cur.second.size() == 1){
                    // printf("adding zero-edge %d-%lld %lld\n", i, v, 0);

                    fg[i].push_back({v,0});
                }
            }
        }              
    }

    // 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]);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void add_change_edge(int, int, int, long long int)':
Main.cpp:37:8: warning: unused variable 'maxw' [-Wunused-variable]
   37 |     ll maxw = g[u][c][0].first;
      |        ^~~~
Main.cpp: In function 'int main()':
Main.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d %d %d %lld", &u,&v,&c,&p);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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