Submission #1176695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176695		paulxaxa	Robot (JOI21_ho_t4)	C++17	0 / 100	195 ms	20676 KiB

Main

#include <bits/stdc++.h>

#define NMAX 100000
#define LOG 20

#define ll long long int
#define BASE 32

#define MOD 1000000007


using namespace std;

ifstream fin("cod.in");
ofstream fout("cod.out");

int n,m;
struct edge
{
    int to,c,p,id;
};


pair<int,int> rid[NMAX+1];
map<pair<int,int>,int> idState;
ll dist[4*NMAX+1];

bool cmpHeap(pair<ll,int> a,pair<ll,int> b)
{
    return a.first > b.first;
}

vector<edge> adj[NMAX+1];

map<int,int> bad[NMAX+1];


int main()
{


    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c,p;
        cin >> a >> b >> c >> p;
        adj[a].push_back({b,c,p,i});
        adj[b].push_back({a,c,p,i});
    }

    rid[1] = {1,0};
    idState[rid[1]]=1;
    bad[1][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(auto e : adj[i])
        {
            if(idState.find({i,e.c})==idState.end())
            {
                idState[make_pair(i,e.c)] = idState.size() + 1;
                rid[idState.size()] = {i,e.c};
            }
            bad[i][e.c]++;
        }

    }


    for(int i=1;i<=idState.size();i++)
    {
        dist[i] = 1e9;
    }


    vector<pair<ll,int>> pq;
    dist[1]=0;
    pq.push_back({0,1});

    while(!pq.empty())
    {
        pop_heap(pq.begin(),pq.end(),cmpHeap);
        int curr = pq.back().second;
        int x = rid[curr].first;
        int c = rid[curr].second;
        ll d = pq.back().first;
        pq.pop_back();

        if(dist[curr]==d)
        {
            for(auto e : adj[x])
            {
                int nxt = idState[{e.to,e.c}];
                int cost = bad[x][e.c]==1 ? 0 : bad[x][e.c] - (c==e.c)-1;
                if(dist[nxt] > dist[curr] + cost)
                {
                    dist[nxt] = dist[curr] + cost;
                    pq.push_back({dist[nxt],nxt});
                    push_heap(pq.begin(),pq.end(),cmpHeap);
                }
            }
        }
    }
    ll res = 1e9;
    for(auto e : adj[n])
    {
        res=min(res,dist[idState[{n,e.c}]]);
    }
    if(res==1e9)
    {
        cout << -1;
    }
    else
    {
        cout << res;
    }



}

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