Submission #1176688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176688		paulxaxa	Robot (JOI21_ho_t4)	C++17	0 / 100	49 ms	17736 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;
};
struct state
{
    ll d;
    int x,t;
    state(ll d,int x,int t)
    {
        this->d = d;
        this->x = x;
        this->t = t;
    }
};
bool cmpHeap(state a,state b)
{
    return a.d > b.d;
}

vector<edge> adj[NMAX+1];

set<int> bad[NMAX+1];
int rem[NMAX+1];
ll dist[NMAX+1][2];


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    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});
    }

    for(int i=1;i<=n;i++)
    {
        map<int,int> freq;
        for(auto e : adj[i])
        {
            if(freq[e.c] > 0)
            {
                rem[i]++;
            }
            freq[e.c]++;
        }
        for(auto e : adj[i])
        {
            if(freq[e.c]>1)
            {
                bad[i].insert(e.id);
            }
        }
    }
//    for(int i=1;i<=n;i++)
//    {
//        dist[i][0] = dist[i][1] = 1e15;
//    }
//    vector<state> pq;
//    dist[1][0] = 0;
//    pq.push_back({0,1,0});
//    while(!pq.empty())
//    {
//        push_heap(pq.begin(),pq.end(),cmpHeap);
//        int x = pq.back().x;
//        int t = pq.back().t;
//        ll d = pq.back().d;
//        pq.pop_back();
//
//        if(d==dist[x][t])
//        {
//            int cost = rem[x] - t;
//            for(auto e : adj[x])
//            {
//                int t1 = bad[e.to].find(e.id) != bad[e.to].end();
//                if(dist[e.to][t1] > dist[x][t] + cost)
//                {
//                    dist[e.to][t1] = dist[x][t] + cost;
//                    pq.push_back({dist[e.to][t1],e.to,t1});
//                    push_heap(pq.begin(),pq.end(),cmpHeap);
//                }
//            }
//        }
//    }
    if(min(dist[n][0],dist[n][1])==1e15)
    {
        cout << -1;
    }
    else
    {
        cout << min(dist[n][0],dist[n][1]);
    }


}

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