Submission #546094

#	Time	Username	Problem	Language	Result	Execution time	Memory
546094		someone	Robot (JOI21_ho_t4)	C++14	100 / 100	1212 ms	127576 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
struct Arc {
    int nex, pds, col;
};
 
struct Sit {
    int i, col, t;
    
    bool operator <(const Sit& other) const {
        return t > other.t;
    }
};
 
const int N = 1e5 + 42, M = 4e5 + 42, INF = 1e18 + 42;
 
int n, m, id = 0;
priority_queue<Sit> q;
vector<Arc> adj[N], adjCol[M];
unordered_map<int, int> idAdj[N];
unordered_map<int, int> tot[N], dist[N];
 
void Dijkstra() {
    while(!q.empty()) {
        Sit sit = q.top();
        q.pop();
        int i = sit.i, col = sit.col, t = sit.t;
        if(t == dist[i][col]) {
            if(col == 0) {
                for(Arc arc : adj[i]) {
                    if(dist[arc.nex][0] > t + min(arc.pds, tot[i][arc.col] - arc.pds)) {
                        dist[arc.nex][0] = t + min(arc.pds, tot[i][arc.col] - arc.pds);
                        q.push({arc.nex, 0, dist[arc.nex][0]});
                    }
                    if(dist[arc.nex][arc.col] > t) {
                        dist[arc.nex][arc.col] = t;
                        q.push({arc.nex, arc.col, t});
                    }
                }
            } else {
                t += tot[i][col];
                int j = idAdj[i][col];
                for(Arc arc : adjCol[j])
                    if(dist[arc.nex][0] > t - arc.pds) {
                        dist[arc.nex][0] = t - arc.pds;
                        q.push({arc.nex, 0, t - arc.pds});
                    }
            }
        }
    }
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a, b, col, pds;
        cin >> a >> b >> col >> pds;
        a--, b--;
        tot[a][col] += pds;
        tot[b][col] += pds;
        adj[a].push_back({b, pds, col});
        adj[b].push_back({a, pds, col});
        dist[a][col] = dist[b][col] = INF;
        if(idAdj[a].find(col) == idAdj[a].end())
            idAdj[a][col] = id++;
        if(idAdj[b].find(col) == idAdj[b].end())
            idAdj[b][col] = id++;
        adjCol[idAdj[a][col]].push_back({b, pds, col});
        adjCol[idAdj[b][col]].push_back({a, pds, col});
    }
    for(int i = 0; i < n; i++)
        dist[i][0] = INF;
    
    for(auto p : dist[0]) {
        q.push({0, p.first, 0});
        dist[0][p.first] = 0;
    }
    
    Dijkstra();
    
    if(dist[n-1][0] == INF)
        cout << -1;
    else
        cout << dist[n-1][0];
}

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