제출 #691304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
691304		Cookie197	Robot (JOI21_ho_t4)	C++17	0 / 100	3042 ms	231068 KiB

Main

// Cookie197 
// the people who invented competitive programming must be ******* crazy
// why am i still here suffering while i can do something else more valuable?
// WHY???
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<iomanip>
#include<math.h>
#include<unordered_map>
#include<numeric>
#include<random>
using namespace std;
#define Why_does_competitive_programming_even_exist ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define pii pair<ll,ll>
#define pdd pair<double ,double>
#define mp make_pair
#define mod 998244353
//#define mod 1000000007
#define endl "\n"
#define inf (ll)1e18
#define out(x) cout << #x << " = " << x <<endl;
#define out2(a,b) cout<< #a << "[" << b << "]" << " = " << a[b] << endl;
#define outp(x) cout << #x << " first = " << x.first << "  second = " << x.second << endl

int n,m;
vector<pii> adj[100005];
ll c[200005], p[200005];
map<pii,int> cnt;
map<pii,int> dist;

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

    int ans = 1e9;
    priority_queue<pair<int,pii>,vector<pair<int,pii> >, greater<pair<int,pii> > > pq;
    pq.push(mp(0,mp(1,0)));
    while(pq.size()){
        int d = pq.top().first, node = pq.top().second.first, color = pq.top().second.second;
        pq.pop();
        if (dist.count(mp(node,color))) continue;
        //cout<<node<<"  "<<ID<<"   "<<d<<endl;
        dist[mp(node,color)] = d;
        if (node == n){
            ans = d;
            break;
        }

        for (pii P:adj[node]){
            int u = P.first, id = P.second;
            //if (id == ID) continue;

            int count = cnt[mp(node,c[id])];
            if (c[id] == color) count--;
            if (count <= 1) pq.push(mp(d,mp(u,0)));
            else pq.push(mp(d+1,mp(u,id)));
        }
    }

    
    
    if (ans == 1e9) cout<<-1<<endl;
    else cout<<ans<<endl;
}

/*
6 10
1 2 1 1
1 3 1 1
1 5 2 1
2 3 2 1
2 5 1 1
2 4 3 1
2 6 1 1
3 4 3 1
4 6 1 1
5 6 2 1
ans = 0
*/

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