Submission #446107

#	Time	Username	Problem	Language	Result	Execution time	Memory
446107		JovanB	Robot (JOI21_ho_t4)	C++17	100 / 100	1377 ms	83884 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];

map <int, 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][c].push_back({b, i});
        graf[b][c].push_back({a, i});
        dist[b][c] = INF;
        dist[a][c] = INF;
        cost[a][c] += p;
        cost[b][c] += p;
        edg[i] = p;
        clr[i] = c;
    }
    dist[1][0] = 0;
    using T = pair <ll, pair <int, int>>;
    priority_queue <T, vector <T>, greater <T>> q;
    q.push({0, {1, 0}});
    while(!q.empty()){
        T prr = q.top();
        q.pop();
        ll dst = prr.first;
        int v = prr.second.first;
        int vcol = prr.second.second;
        if(dist[v][vcol] != dst) continue;
        if(vcol == 0){
            for(auto &colors : graf[v]){
                for(auto pr : colors.second){
                    int c = pr.first;
                    int koja = pr.second;
                    ll p = edg[koja];
                    int col = clr[koja];
                    ll sve = cost[v][col] - p;
                    ll nd;
                    /// 1 - nije bitno da li menjam granu
                    nd = dst + min(sve, p);
                    if(dist[c][0] > nd){
                        dist[c][0] = nd;
                        q.push({dist[c][0], {c, 0}});
                    }
                    /// 2 - menjam granu (i sve iste boje kod c), bitna je
                    nd = dst;
                    if(dist[c][col] > nd){
                        dist[c][col] = nd;
                        q.push({nd, {c, col}});
                    }
                }
            }
        }
        else{
            for(auto pr : graf[v][vcol]){
                int c = pr.first;
                int koja = pr.second;
                int p = edg[koja];
                ll nd = dst + cost[v][vcol] - p;
                if(dist[c][0] > nd){
                    dist[c][0] = nd;
                    q.push({nd, {c, 0}});
                }
            }
        }
    }
    ll mn = dist[n][0];
    if(mn == INF) cout << "-1\n";
    else cout << mn << "\n";
    return 0;
}

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