Submission #1033029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033029		MinhBoss	Robot (JOI21_ho_t4)	C++14	100 / 100	983 ms	112624 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define int long long

const ll MOD = 1e9+7;
void add(ll &x, const ll y){
    x+= y;
    if(x>=MOD) x-= MOD;
}
bool maximize(ll &x, const ll y){
    if(x < y){
        x = y; return true;
    }
    return false;
}
bool minimize(ll &x, const ll y){
    if(x > y){
        x = y; return true;
    }
    return false;
}

const ll MAX = 2e5+10, INF = 1e18;

ll n,m;
ll dp[MAX];
map<ll,ll>dp2[MAX], costSum[MAX];

struct Edge{
    ll from, to, color, cost;
    Edge(ll _from=0, ll _to=0, ll _color=0, ll _cost=0){
        from = _from;
        to = _to;
        color = _color;
        cost = _cost;
    }
};
map<ll,vector<Edge>>adj[MAX];


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

//    freopen("shortcut.in","r",stdin);
//    freopen("shortcut.out","w",stdout);
    cin>>n>>m;
    for(int i =1;i<=m;i++){
        ll u,v,c,p;
        cin>>u>>v>>c>>p;
        adj[u][c].pb(Edge(u,v,c,p));
        adj[v][c].pb(Edge(v,u,c,p));
        costSum[u][c] += p;
        costSum[v][c] += p;
    }
    memset(dp, 0x3f, sizeof dp);

    priority_queue<vector<ll>>q;
    dp[1] = 0;
    q.push({0,1,0});

    while(!q.empty()){
        ll u = q.top()[1], c = q.top()[2], cost = q.top()[0];
        q.pop();

        if(c){
            if(dp2[u][c] != -cost) continue;
            ll case3 = costSum[u][c] - cost;
            for(auto e : adj[u][c]){
                if(case3 - e.cost < dp[e.to]){
                    dp[e.to] = case3 - e.cost;
                    q.push({-dp[e.to], e.to, 0});
                }
            }

        }
        else{
            if(dp[u] != -cost) continue;
            for(auto &j : adj[u]){
                for(auto e : j.se){
                    ll case1 = e.cost - cost;
                    if(case1 < dp[e.to]){
                        dp[e.to]= case1;
                        q.push({-dp[e.to], e.to,0});
                    }


                    ll case2 = costSum[u][e.color] - cost - e.cost;
                    if(case2 < dp[e.to]){
                        dp[e.to] = case2;
                        q.push({-dp[e.to], e.to, 0});
                    }

                    ll case3 = -cost;
                    if(!dp2[e.to].count(e.color) || dp2[e.to][e.color] > case3){
                        dp2[e.to][e.color] = case3;
                        q.push({-dp2[e.to][e.color], e.to, e.color});
                    }
                }
            }
        }



    }

    cout<<(dp[n] >= INF ? -1 : dp[n])<<endl;
}

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