oj.uz

답안 #894495

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
894495 2023-12-28T11:15:13 Z hafo Robot (JOI21_ho_t4) C++14
100 / 100
 677 ms 102192 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e18 + 69;

int n, m, u, v, c, p;
struct edge {
    int v, c, p;
};
map<int, vector<edge>> g[maxn];
ll f[maxn];
map<int, ll> f2[maxn], cnt[maxn];

struct state {
    ll cost;
    int u, c;

    friend bool operator < (const state &a, const state &b) {
        return a.cost > b.cost;
    } 

};

void dijkstra() {
    priority_queue<state> q;
    fill_n(f, n + 1, oo);
    f[1] = 0;
    q.push({0, 1, 0});

    while(!q.empty()) {
        int u = q.top().u, c = q.top().c;
        ll fu = q.top().cost;
        q.pop();

        if(c > 0) {
            if(f2[u][c] != fu) continue;
            for(auto e:g[u][c]) {
                int v = e.v;
                if(mini(f[v], fu + cnt[u][c] - e.p)) {
                    q.push({f[v], v, 0});
                }
            }
        } else {
            if(f[u] != fu) continue;
            for(auto tmp:g[u]) {
                for(auto e:tmp.se) {
                    int v = e.v;
                    if(mini(f[v], fu + cnt[u][e.c] - e.p)) {
                        q.push({f[v], v, 0});
                    }
                    if(mini(f[v], fu + e.p)) {
                        q.push({f[v], v, 0});
                    }
                    if(!f2[v].count(e.c) || f2[v][c] > fu) {
                        f2[v][e.c] = fu;
                        q.push({fu, v, e.c});
                    }
                }
            }
        }
    }

    cout<<(f[n] == oo ? -1:f[n]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>m;
    while(m--) {
        cin>>u>>v>>c>>p;
        g[u][c].pb({v, c, p});
        g[v][c].pb({u, c, p});
        cnt[u][c] += p;
        cnt[v][c] += p;
    }

    dijkstra();
    return 0;
}

Subtask #1
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 30044 KB Output is correct
2 Correct 6 ms 30044 KB Output is correct
3 Correct 6 ms 30044 KB Output is correct
4 Correct 6 ms 30044 KB Output is correct
5 Correct 6 ms 30044 KB Output is correct
6 Correct 6 ms 30044 KB Output is correct
7 Correct 7 ms 30164 KB Output is correct
8 Correct 6 ms 30296 KB Output is correct
9 Correct 9 ms 30716 KB Output is correct
10 Correct 10 ms 31140 KB Output is correct
11 Correct 8 ms 30552 KB Output is correct
12 Correct 7 ms 30584 KB Output is correct
13 Correct 8 ms 30556 KB Output is correct
14 Correct 8 ms 30428 KB Output is correct
15 Correct 8 ms 30524 KB Output is correct
16 Correct 8 ms 30556 KB Output is correct
17 Correct 8 ms 30556 KB Output is correct
18 Correct 6 ms 30300 KB Output is correct
19 Correct 8 ms 30296 KB Output is correct
20 Correct 7 ms 30808 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 49096 KB Output is correct
2 Correct 53 ms 39884 KB Output is correct
3 Correct 129 ms 44136 KB Output is correct
4 Correct 73 ms 42956 KB Output is correct
5 Correct 677 ms 96480 KB Output is correct
6 Correct 564 ms 90644 KB Output is correct
7 Correct 266 ms 72528 KB Output is correct
8 Correct 270 ms 69460 KB Output is correct
9 Correct 276 ms 69456 KB Output is correct
10 Correct 233 ms 63996 KB Output is correct
11 Correct 93 ms 46676 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 30044 KB Output is correct
2 Correct 6 ms 30044 KB Output is correct
3 Correct 6 ms 30044 KB Output is correct
4 Correct 6 ms 30044 KB Output is correct
5 Correct 6 ms 30044 KB Output is correct
6 Correct 6 ms 30044 KB Output is correct
7 Correct 7 ms 30164 KB Output is correct
8 Correct 6 ms 30296 KB Output is correct
9 Correct 9 ms 30716 KB Output is correct
10 Correct 10 ms 31140 KB Output is correct
11 Correct 8 ms 30552 KB Output is correct
12 Correct 7 ms 30584 KB Output is correct
13 Correct 8 ms 30556 KB Output is correct
14 Correct 8 ms 30428 KB Output is correct
15 Correct 8 ms 30524 KB Output is correct
16 Correct 8 ms 30556 KB Output is correct
17 Correct 8 ms 30556 KB Output is correct
18 Correct 6 ms 30300 KB Output is correct
19 Correct 8 ms 30296 KB Output is correct
20 Correct 7 ms 30808 KB Output is correct
21 Correct 155 ms 49096 KB Output is correct
22 Correct 53 ms 39884 KB Output is correct
23 Correct 129 ms 44136 KB Output is correct
24 Correct 73 ms 42956 KB Output is correct
25 Correct 677 ms 96480 KB Output is correct
26 Correct 564 ms 90644 KB Output is correct
27 Correct 266 ms 72528 KB Output is correct
28 Correct 270 ms 69460 KB Output is correct
29 Correct 276 ms 69456 KB Output is correct
30 Correct 233 ms 63996 KB Output is correct
31 Correct 93 ms 46676 KB Output is correct
32 Correct 87 ms 41968 KB Output is correct
33 Correct 93 ms 44232 KB Output is correct
34 Correct 298 ms 66496 KB Output is correct
35 Correct 200 ms 57828 KB Output is correct
36 Correct 238 ms 65016 KB Output is correct
37 Correct 292 ms 67896 KB Output is correct
38 Correct 266 ms 72460 KB Output is correct
39 Correct 90 ms 45012 KB Output is correct
40 Correct 285 ms 70916 KB Output is correct
41 Correct 290 ms 71020 KB Output is correct
42 Correct 387 ms 77864 KB Output is correct
43 Correct 131 ms 52228 KB Output is correct
44 Correct 246 ms 56776 KB Output is correct
45 Correct 248 ms 66132 KB Output is correct
46 Correct 200 ms 66924 KB Output is correct
47 Correct 251 ms 68108 KB Output is correct
48 Correct 654 ms 102192 KB Output is correct