Submission #1064625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064625		dpsaveslives	Robot (JOI21_ho_t4)	C++17	100 / 100	644 ms	86720 KiB

Main

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5+10;
struct edge{
    int v,c; ll p;
};
vector<int> res[MAXN];
map<int,ll> sum[MAXN],dp2[MAXN];
map<int,vector<edge>> adj[MAXN];
ll dp[MAXN];
const ll INF = 1e18;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N,M; cin >> N >> M;
    for(int i = 0;i<M;++i){
        int a,b,c; ll p; cin >> a >> b >> c >> p;
        adj[a][c].push_back({b,c,p});
        sum[a][c] += p;
        adj[b][c].push_back({a,c,p});
        sum[b][c] += p;
    }
    memset(dp,0x3f,sizeof(dp));
    dp[1] = 0; priority_queue<tuple<ll,int,int>> pq; pq.push({0,1,0});
    while(!pq.empty()){
        ll cd; int u,c; tie(cd,u,c) = pq.top(); pq.pop();
        if(c){
            if(dp2[u][c] != -cd) continue;
            for(auto x : adj[u][c]){
                ll nd = sum[u][c]-x.p-cd;
                if(dp[x.v] > nd){
                    dp[x.v] = nd;
                    pq.push({-nd,x.v,0});
                }
            }
        }
        else{
            if(dp[u] != -cd) continue;
            for(auto col : adj[u]){
                for(auto x : col.second){
                    ll one = sum[u][x.c]-x.p-cd;
                    if(one < dp[x.v]){
                        dp[x.v] = one;
                        pq.push({-one,x.v,0});
                    }
                    ll two = x.p-cd;
                    if(two < dp[x.v]){
                        dp[x.v] = two;
                        pq.push({-two,x.v,0});
                    }
                    ll three = -cd;
                    if(!dp2[x.v].count(x.c) || three < dp2[x.v][x.c]){
                        dp2[x.v][x.c] = three;
                        pq.push({-three,x.v,x.c});
                    }
                }
            }
        }
    }
    if(dp[N] > INF){
        cout << -1 << "\n";
    }
    else{
        cout << dp[N] << "\n";
    }
    return 0;
}

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