Submission #645813

#	Time	Username	Problem	Language	Result	Execution time	Memory
645813		swagchicken	Robot (JOI21_ho_t4)	C++14	24 / 100	1920 ms	131560 KiB

Main

/*
 ID: swagchicken1
 PROG:
 LANG: C++11
 */
 
#include <iostream>
#include <tuple>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iomanip>
#include <ctime>
#include <cctype>
#include <climits>
#include <chrono>
#include <numeric>
#include <functional>
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
 
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)
#define all(a) a.begin(), a.end()
#define endl '\n';
#define sz(x) (int)(x).size()
 
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
 
template <typename T>
void pr(vector<T> &v) {
    FOR(i, 0, sz(v)) cout << v[i] << " ";
    cout << endl;
}
template <typename T>
void pr(vector<vector<T> > &v) {
    FOR(i, 0, sz(v)) { pr(v[i]); }
}
template <typename T>
void re(T &x) {
    cin >> x;
}
template <typename T>
void re(vector<T> &a) {
    FOR(i, 0, sz(a)) re(a[i]);
}
template <class Arg, class... Args>
void re(Arg &first, Args &... rest) {
    re(first);
    re(rest...);
}
template <typename T>
void pr(T x) {
    cout << x << endl;
}
template <class Arg, class... Args>
void pr(const Arg &first, const Args &... rest) {
    cout << first << " ";
    pr(rest...);
    cout << endl;
}
void ps() { cout << endl; }
template<class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
    cout << t; if (sizeof...(ts)) cout << " "; ps(ts...);
}
 
const ll MOD  = 1000000007;
#define inf 1e18;
#define INF INT_MAX
//#define DEBUG
 
long double PI = 4*atan(1);
long double eps = 1e-9;


vector<vector<pair<int, ll>>> adj;
map<pii, ll> weights;
map<pii, ll> cols;
map<int, map<int, vector<int>>> nodecols;
vector<pii> edges;
vector<ll> dist;

void dijkstra(int start) {
    int N = dist.size();
    FOR(i,0,N) dist[i] = 1e18;
    dist[start] = 0;
    set<pair<ll, int>> pq;
    pq.insert({0, start});
    while(!pq.empty()) {
        pair<ll, int> curr = *pq.begin();
        pq.erase(pq.find(curr));
        int u = curr.ss;
        ll d = curr.ff;
        for(pair<int, ll> nxt : adj[u]) {
            int v = nxt.ff; ll w = nxt.ss;
            if(d + w < dist[v]) {
                if(pq.find({dist[v], v}) != pq.end()) pq.erase(pq.find({dist[v], v}));
                dist[v] = d+w;
                pq.insert({d + w, v});
            }
        }
    }
}



int main() {
    //auto start = chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);cin.tie(0);
    //ofstream cout("output.txt");
    //ifstream cin("input.txt");
    #ifdef DEBUG
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        // freopen("cowmbat.in", "r", stdin);
        // freopen("cowmbat.out", "w", stdout);
    #endif

    int n,m; cin >> n >> m;
    adj.resize(n);
    dist.resize(n);
    FOR(i,0,m) {
        int u,v; cin >> u >> v; u--; v--;
        ll c,p; cin >> c >> p;
        edges.pb({u,v});
        weights[{u,v}] = p;
        cols[{u,v}] = c;
        nodecols[u][c].pb(v);
        nodecols[v][c].pb(u);
    }
    int tot = n;

    for(pii x : edges) {
        int u = x.ff, v = x.ss;
        int c = cols[{u,v}];
        ll cost = weights[{u,v}];
        int cnt1 = nodecols[u][c].size();
        int cnt2 = nodecols[v][c].size();

        // cout << u << " " << v << endl;
        // cout << c << endl;
        // cout << cnt1 << " " << cnt2 << endl;
        // cout << endl;
        if(cnt1 == 2) {
            vector<pair<int, ll>> newnode;
            adj.pb(newnode);
            adj[v].pb({tot, cost});
            adj[u].pb({tot, cost});
            adj[tot].pb({u, 0});
            int other = ((nodecols[u][c][0] != v) ? nodecols[u][c][0] : nodecols[u][c][1]);
            adj[tot].pb({other, 0});
            dist.pb(0);
            tot++;
        }
        if(cnt2 == 2) {
            vector<pair<int, ll>> newnode;
            adj.pb(newnode);
            adj[u].pb({tot, cost});
            adj[v].pb({tot, cost});
            adj[tot].pb({v, 0});
            int other = ((nodecols[v][c][0] != u) ? nodecols[v][c][0] : nodecols[v][c][1]);
            adj[tot].pb({other, 0});
            dist.pb(0);
            tot++;
        } 
        if(cnt1 == 1) {
            adj[u].pb({v, 0});
        }
        if(cnt2 == 1) {
            adj[v].pb({u, 0});
        }
        if(cnt1 > 1) {
            adj[u].pb({v, cost});   
        }
        if(cnt2 > 1) {
            adj[v].pb({u, cost});
        }
    }

    // FOR(i,0,tot) {
    //     cout << "NODE " << i << endl;
    //     for(pair<int, ll> x : adj[i]) {
    //         cout << x.ff << " "  << x.ss << endl;
    //     }
    //     cout << "----------" << endl;
    // }

    dijkstra(0);

    cout << ((dist[n-1] == 1e18) ? -1 : dist[n-1]) << endl;


    
    //auto stop = chrono::high_resolution_clock::now();
    //auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
    //cout << duration.count() << endl;
    //cin.close();
    //cout.close();
}
    

    

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