Submission #1108572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108572		chaoslong	Robot (JOI21_ho_t4)	C++14	0 / 100	82 ms	46780 KiB

Main

// Calm down.
// Think three times, code twice.
#include "bits/stdc++.h"
#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <ll,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

using namespace std;
const int N = 2e5 + 5;
const int mod = 1e9 + 7; // 998244353
const ll oo = 1e18;

struct edge {
    int u, c; ll p;
};

struct sth {
    int u, c; ll p;
    bool operator < (const sth &y) const {
        return p < y.p;
    }
};

int n, m, dem[N];
ll dp[N];
map<int, ll> dp2[N], sum[N];
map<int, vector<edge>> a[N];

void to_nho_cau() {
    cin >> n >> m;
    forr(i, 1, m) {
        int u, v, c; ll p;
        cin >> u >> v >> c >> p;
        a[u][c].pb({v, c, p});
        a[v][c].pb({u, c, p});
        sum[u][c] += p;
        sum[v][c] += p;
    }
    priority_queue<sth, vector<sth>> q;
    memset(dp, 63, sizeof dp);
    q.push({1, 0, 0LL}); dp[1] = 0;
    while(q.size()) {
        int u = q.top().u, c = q.top().c; ll du = q.top().p; q.pop();
        if(c) {
            if(du > dp2[u][c]) continue;
            dem[u]++; if(dem[u] > 100) break;
            for(edge e: a[u][c]) {
                ll cost = sum[u][c] - e.p + du;
//                    cout << cost << " " << u << " " << e.u << " 3\n";
                if(cost < dp[e.u] && cost >= 0) {
                    dp[e.u] = cost;
                    q.push({e.u, 0, dp[e.u]});
                }
            }
        } else {
            if(du > dp[u]) continue;
            dem[u]++; if(dem[u] > 100) break;
            for(map<int, vector<edge>>::iterator it = a[u].begin(); it != a[u].end(); it++) {
                for(edge e: it->nd) {
                    ll cost = sum[u][e.c] - e.p + du;
                    if(cost < dp[e.u] && cost >= 0) {
//                        cout << cost << " " << u << " " << e.u << " 1\n";
                        dp[e.u] = cost;
                        q.push({e.u, 0, dp[e.u]});
                    }
                    cost = e.p + du;
                    if(cost < dp[e.u] && cost >= 0) {
//                        cout << cost << " " << u << " " << e.u << " 2\n";
                        dp[e.u] = cost;
                        q.push({e.u, 0, dp[e.u]});
                    }
                    cost = du;
                    if(!dp2[e.u].count(e.c)) dp2[e.u][e.c] = oo;
                    if(cost < dp2[e.u][e.c] && cost >= 0) {
                        dp2[e.u][e.c] = cost;
                        q.push({e.u, e.c, cost});
                    }
                }
            }
        }
    }
//    cout << dp[2] << "\n";
    if(dp[n] < oo) {
        cout << dp[n] << "\n";
    } else cout << -1 << "\n";
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    #ifdef LOCAL
        freopen(file".inp","r",stdin);
        freopen(file".out","w",stdout);
    #endif // LOCAL
    int t = 1;
//    cin >> t;
    while(t--) to_nho_cau();
}
/*
1.self check:
2.long long
3.size of array
4.code for testing
5.initializing
6.modulo number
*/

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