Submission #1320380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320380		Vu_CG_Coder	Robot (JOI21_ho_t4)	C++20	0 / 100	162 ms	45064 KiB

Main

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define pb push_back
#define vec vector
#define um unordered_map
#define us unordered_set
#define ms multiset

#define cocainit ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define koconcainit return 0;
#define debug(x) cout << x << ' ';
#define For(i, a, b) for(int i = a; i <= b; ++i)
#define Forn(i, b, a) for(int i = b; i >= a; --i)
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define MASK(i) (1 << (i))
#define BIT(i, x) (((x) >> (i)) & 1)
#define fileinp(x) freopen((x + ".inp").c_str(), "r", stdin)
#define fileout(x) freopen((x + ".out").c_str(), "w", stdout)
#define iiiiii iiiiii
const ll INF = (ll)4e18;
const int mx = 2e5 + 5;
const int mx2 = 5e5 + 5;
const int dx[] = {-2, -2, -1, 1, 2, 2, 1, -1};
const int dy[] = {-1, 1, 2, 2, 1, -1, -2, -2};
const int MOD = 1e9 + 7;
const int MOD2 = 14062008;


struct edge{
    int u,v,c;
    ll w;
};

int s,k;
vec<edge> e;
vec<vec<pair<int,ll>>> a;

void dijkstra(){
    vec<ll> d(s + 1, INF);
    priority_queue<pair<ll,int>, vec<pair<ll,int>>, greater<pair<ll,int>>> pq;
    d[1]=0;
    pq.push({0, 1});

    while(!pq.empty()){
        auto [du,u] = pq.top(); pq.pop();
        if(du!=d[u]) continue;
        for(auto [v,w]:a[u]){
            if(d[v] > du + w){
                d[v] = du + w;
                pq.push({d[v],v});
            }
        }
    }
    cout << (d[s] >= INF / 2 ? -1 : d[s]);
}

signed main(){
    cocainit;

    cin >> s >> k;
    e.clear();
    a.assign(s + 1,{});

    For(i, 1, k){
        int u,v,c; ll w;
        cin >> u >> v >> c >> w;
        e.pb({u, v, c, w});
    }

    vec<unordered_map<int,ll>> sum(s + 1);
    for(auto &x: e){
        sum[x.u][x.c] += x.w;
        sum[x.v][x.c] += x.w;
    }

    for(auto &x:e){
        ll su = sum[x.u][x.c];
        ll sv = sum[x.v][x.c];
        ll cu = min(x.w, su - x.w);
        ll cv = min(x.w, sv - x.w);
        a[x.u].pb({x.v, cu});
        a[x.v].pb({x.u, cv});
    }

    dijkstra();
    koconcainit;
}

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