Submission #1161729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161729		tw20000807	Robot (JOI21_ho_t4)	C++20	100 / 100	595 ms	65160 KiB

Main

#include<bits/stdc++.h>
#define int long long
#define all(v) v.begin(), v.end()
#define SZ(x) (int)x.size()
#define pii pair<int, int>
#define X first
#define Y second

using namespace std;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;//    998244353;
const int llmx = 1e18;


void sol(){
    int n, m;
    cin >> n >> m;
    vector< vector< array<int, 3> > > g(n + 1);
    vector< map<int, int> > cnt(n + 1);
    vector< map<int, int> > dis(n + 1);   
    while(m--){
        int a, b, c, p;
        cin >> a >> b >> c >> p;
        cnt[a][c] += p;
        cnt[b][c] += p;
        g[a].push_back({c, p, b});
        g[b].push_back({c, p, a});
    }
    for(int i = 1; i <= n; ++i) sort(all(g[i]));
    priority_queue< array<int, 3>, vector< array<int, 3> >, greater< array<int, 3> > > pq;

    dis[1][0] = 0;
    pq.push({0, 1, 0}); 

    while(!pq.empty()){
        auto [D, cur, col] = pq.top(); pq.pop();
        if(dis[cur][col] != D) continue;

        for(auto it = lower_bound(all(g[cur]), array<int, 3>{col, 0, 0}); it != g[cur].end() && (col == 0 || it->at(0) == col); ++it){
            auto [c, p, nxt] = *it;

            if(!dis[nxt].count(c)) dis[nxt][c] = llmx;
            if(!dis[nxt].count(0)) dis[nxt][0] = llmx;

            if(col == 0){
                if(dis[nxt][0] > D + min(cnt[cur][c] - p, p)){
                    dis[nxt][0] = D + min(cnt[cur][c] - p, p);
                    pq.push({dis[nxt][0], nxt, 0});
                }
                if(dis[nxt][c] > D){
                    dis[nxt][c] = D;
                    pq.push({dis[nxt][c], nxt, c});
                }
            }
            else if(dis[nxt][0] > D + cnt[cur][c] - p){
                dis[nxt][0] = D + cnt[cur][c] - p;
                pq.push({dis[nxt][0], nxt, 0});
            }
        }
    }
    if(!dis[n].count(0) || dis[n][0] == llmx) cout << "-1\n";
    else cout << dis[n][0] << "\n";
}
/*
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

// 3

5 2
1 4 1 2
3 5 1 4
// -1


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
// 1

13 21
7 10 4 4
3 6 4 7
8 10 4 5
3 9 2 5
1 4 4 5
2 6 4 2
3 11 2 2
3 8 16 2
8 11 16 1
6 10 4 14
6 8 16 6
9 12 16 5
5 13 4 6
1 12 4 7
2 4 4 18
2 9 4 10
2 12 4 6
10 13 4 28
5 7 2 5
5 11 2 16
7 13 4 20

// 7


*/
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cerr.tie(0);
    int t = 1; //cin >> t;
    while(t--) sol();
}

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