Submission #1040750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040750		TAhmed33	Robot (JOI21_ho_t4)	C++98	34 / 100	3041 ms	81556 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e16;
const int MAXN = 2e5 + 25;
int n, m;
vector <array <ll, 3>> adj[MAXN];
map <ll, ll> dist[MAXN][2];
priority_queue <array <ll, 4>, vector <array <ll, 4>>, greater <>> pq;
    void solve () {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        adj[a].push_back({b, c, d});
        adj[b].push_back({a, c, d});
    }  
    pq.push({0, 1, 0, -1});
    dist[1][0][-1] = 0;
    while (!pq.empty()) {
        auto k = pq.top();
        pq.pop();
        if (k[0] > dist[k[1]][k[2]][k[3]]) {
            continue;
        }
        map <int, int> freq;
        map <int, ll> sum;
        for (auto j : adj[k[1]]) {
            if (k[2]) {
                if (j[0] != k[3]) {
                    freq[j[1]]++;
                    sum[j[1]] += j[2];
                }
            } else {
                freq[j[1]]++;
                sum[j[1]] += j[2];
            }
        }
        for (auto j : adj[k[1]]) {
            if (j[0] != k[3]) {
                if (freq[j[1]] == 1) {
                    if (!dist[j[0]][0].count(k[1]) || dist[j[0]][0][k[1]] > k[0]) {
                        dist[j[0]][0][k[1]] = k[0];
                        pq.push({k[0], j[0], 0, k[1]});
                    } 
                } else {
                    ll c = j[2];
                    if (!dist[j[0]][1].count(k[1]) || dist[j[0]][1][k[1]] > k[0] + c) {
                        dist[j[0]][1][k[1]] = k[0] + c;
                        pq.push({k[0] + c, j[0], 1, k[1]});
                    }  
                    c = sum[j[1]] - j[2];
                    if (!dist[j[0]][0].count(k[1]) || dist[j[0]][0][k[1]] > k[0] + c) {
                        dist[j[0]][0][k[1]] = k[0] + c;
                        pq.push({k[0] + c, j[0], 0, k[1]});
                    }  
                }
            }
        }
    }
    ll mn = inf;
    for (auto j : adj[n]) {
        if (dist[n][0].count(j[0])) mn = min(mn, dist[n][0][j[0]]);
        if (dist[n][1].count(j[0])) mn = min(mn, dist[n][1][j[0]]);
    }
    cout << (mn == inf ? -1 : mn) << '\n';
}       
signed main () {
    ios::sync_with_stdio(0); cin.tie(0);
    int tc = 1; //cin >> tc;
    while (tc--) solve();
}

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