제출 #1176698

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1176698		paulxaxa	Robot (JOI21_ho_t4)	C++17	0 / 100	220 ms	19820 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});

    dist[1]=0;
    deque<int> Q;
    Q.push_back(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 : c!=e.c;
//                if(dist[nxt] > dist[curr] + cost)
//                {
//                    dist[nxt] = dist[curr] + cost;
//                    pq.push_back({dist[nxt],nxt});
//                    push_heap(pq.begin(),pq.end(),cmpHeap);
//                }
//            }
//        }
//    }

    while(!Q.empty())
    {
        int curr = Q.front();
        int x = rid[curr].first;
        int c = rid[curr].second;
        Q.pop_front();

        for(auto e : adj[x])
        {
            int cost = bad[x][e.c] == 1 ? 0 : (c!=e.c);
            int nxt = idState[{e.to,e.c}];
            if(dist[nxt] > dist[curr] + cost)
            {
                dist[nxt] = cost + 1;
                if(cost == 1)
                {
                    Q.push_back(nxt);
                }
                else
                {
                    Q.push_front(nxt);
                }
            }
        }
    }
    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