Submission #446105

#	Time	Username	Problem	Language	Result	Execution time	Memory
446105		JovanB	Robot (JOI21_ho_t4)	C++17	34 / 100	3072 ms	75436 KiB

Main

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

using ll = long long;
using ld = long double;

const int N = 100000;

map <int, ll> dist[N+5];
map <int, ll> cost[N+5];

vector <pair <int, int>> graf[N+5];

const ll INF = 1000000000000000000LL;

const int M = 200000;

ll edg[M+5];
int clr[M+5];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        dist[i][0] = INF;
    }
    for(int i=1; i<=m; i++){
        int a, b, c, p;
        cin >> a >> b >> c >> p;
        graf[a].push_back({b, i});
        graf[b].push_back({a, i});
        dist[b][i] = INF;
        dist[a][i] = INF;
        cost[a][c] += p;
        cost[b][c] += p;
        edg[i] = p;
        clr[i] = c;
    }
    dist[1][0] = 0;
    set <pair <ll, pair <int, int>>> q;
    q.insert({0, {1, 0}});
    while(!q.empty()){
        pair <int, int> prr = q.begin()->second;
        q.erase(q.begin());
        int v = prr.first;
        int od = prr.second;
        ll dst = dist[v][od];
        for(auto tp : graf[v]){
            int c = tp.first;
            int koja = tp.second;
            int col = clr[koja];
            ll sve = cost[v][col] - edg[koja];
            if(od && clr[od] == col) sve -= edg[od];
            /// bojim tu
            ll nd = dst + edg[koja];
            ll dd = dist[c][koja];
            if(dd > nd){
                q.erase({dd, {c, koja}});
                dist[c][koja] = nd;
                q.insert({nd, {c, koja}});
            }
            /// bojim ostale
            nd = dst + sve;
            dd = dist[c][0];
            if(dist[c][0] > nd){
                q.erase({dd, {c, 0}});
                dist[c][0] = nd;
                q.insert({nd, {c, 0}});
            }
        }
    }
    ll mn = INF;
    for(auto x : dist[n]) mn = min(mn, x.second);
    if(mn == INF) cout << "-1\n";
    else cout << mn << "\n";
    return 0;
}

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