Submission #1215450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215450		Mike_Vu	Robot (JOI21_ho_t4)	C++17	0 / 100	94 ms	20984 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define BITJ(x, j) (((x)>>(j))&1)
#define MASK(j) (1LL<<(j))
#define ALL(v) v.begin(), v.end()

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

struct edge{
    int v, p, c;
    edge(int _v, int _p, int _c) {
        v = _v;
        p = _p;
        c = _c;
    }
    void takeval(int &_v, int &_p, int &_c) {
        _v = v;
        _p = p;
        _c = c;
    }
};
bool cmpedge(const edge &a, const edge &b) {
    if (a.c != b.c) return a.c < b.c;
    return a.p < b.p;
}

const int maxn = 1e5+5;
const ll INF = (ll)3e18+7;
int n, m;
vector<edge> rawadj[maxn];
vector<pair<int, ll>> adj[maxn];
ll dis[maxn];

void fixedge(int u) {
    sort(ALL(rawadj[u]), cmpedge);
    ll sumw = 0;
    for (int i = 0; i < (int)rawadj[u].size(); i++) {
        int v, p, c;
        ll w;
        rawadj[u][i].takeval(v, p, c);
        //independent -> 0
        //dependent: itself or all others
        //new
        if (i == 0 || c != rawadj[u][i-1].c) {
            sumw = 0;
        }
        //check same
        if ((i > 0 && c == rawadj[u][i-1].c) ||
            (i < (int)rawadj[u].size()-1 && c == rawadj[u][i+1].c)){
            w = p;
            //if largest
            if (i == (int)rawadj[u].size()-1 || c != rawadj[u][i+1].c) {
                minimize(w, sumw);
            }
            sumw += p;
        }
        else {
            w = 0;
        }
        adj[u].pb({v, w});
//        cout << u << ' ' << v << ' ' << w << "\n";
    }
}

void dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<pair<ll, int>> q;
    q.push({0, 1});
    dis[1] = 0;
    while (!q.empty()) {
        int u = q.top().se;
        ll w = -q.top().fi;
        q.pop();
        if (w != dis[u]) continue;
        for (pii cur : adj[u]) {
            int v = cur.fi;
            ll w = cur.se;
            if (minimize(dis[v], dis[u]+w)) {
                q.push({-dis[v], v});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    cin >> n >> m;
    //input 1 bidi -> 2 unidi
    for (int i = 1; i <= m; i++) {
        int u, v, p, c;
        cin >> u >> v >> c >> p;
        rawadj[u].pb(edge(v, p, c));
        rawadj[v].pb(edge(u, p, c));
    }
    //consider each node
    for (int i = 1; i <= n; i++) {
        fixedge(i);
    }
    //dijkstra in final graph -> ans
    dijkstra();
    cout << (dis[n] > INF ? -1 : dis[n]);
}
/*
5 7
2 3 7 1
1 4 5 1
4 5 3 1
3 4 7 1
2 4 3 1
3 5 6 1
1 2 5 1

5 2
1 4 1 2
3 5 1 4

4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2
*/

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