Submission #915777

#	Time	Username	Problem	Language	Result	Execution time	Memory
915777		ace5	Robot (JOI21_ho_t4)	C++17	100 / 100	1236 ms	77488 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int int64_t

const int INF = 1e18;

struct edge
{
    edge(int _v,int _to,int _c,int _p){v = _v;to = _to;c = _c;p = _p;};
    edge(){v = 0;to = 0;c = 0;p = 0;};
    int v;
    int to;
    int c;
    int p;
};

vector<vector<int>> g;
vector<map<int,vector<int>>> rc;
vector<map<int,int>> sum;
vector<edge> e;
vector<int> dist;
vector<int> vis;
set<pair<int,int>> ff;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    g.resize(n);
    rc.resize(n);
    sum.resize(n);
    for(int j = 0;j < m;++j)
    {
        int u,v,c,p;
        cin >> u >> v >> c >> p;
        u--;
        v--;
        e.push_back(edge(u,v,c,p));
        g[u].push_back(j);
        g[v].push_back(j);
        sum[u][c] += p;
        sum[v][c] += p;
        rc[u][c].push_back(j);
        rc[v][c].push_back(j);
    }
    for(int j = 0;j < n;++j)
    {
        for(auto& c:rc[j])
        {
            sort(c.second.begin(),c.second.end(),[&](int ind1,int ind2){return e[ind1].p > e[ind2].p;});
        }
    }
    dist.resize(n);
    vis.resize(n);
    for(int j =0 ;j < n;++j)
    {
        dist[j] = INF;
        vis[j] = 0;
    }
    dist[0] =0;
    ff.insert({0,0});
    while(ff.size())
    {
        int v = (*ff.begin()).second;
        ff.erase(ff.begin());
        vis[v] = 1;
        for(auto ind:g[v])
        {
            int u = e[ind].v + e[ind].to - v;
            int64_t nu = dist[v] + min(e[ind].p,sum[v][e[ind].c]-e[ind].p);
            if(!vis[u] && dist[u] > nu)
            {
                ff.erase({dist[u],u});
                dist[u] = nu;
                ff.insert({dist[u],u});
            }
            if(rc[u][e[ind].c].size() >= 2)
            {
                int ind2 = (rc[u][e[ind].c][0] == ind ? rc[u][e[ind].c][1] : rc[u][e[ind].c][0]);
                int64_t v2 = e[ind2].v+e[ind2].to-u;
                if(!vis[v2] && dist[v2] > dist[v] + sum[u][e[ind2].c] - e[ind2].p)
                {
                    ff.erase({dist[v2],v2});
                    dist[v2] = dist[v] + sum[u][e[ind2].c] - e[ind2].p;
                    ff.insert({dist[v2],v2});
                }
            }
        }
    }
    cout << (dist[n-1] == INF ? -1 : dist[n-1]);
    return 0;
}

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