QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#532718#5081. Forbidden TurnsBongoCatEnjoyer#TL 134ms19008kbC++141.9kb2024-08-25 10:09:532024-08-25 10:09:54

Judging History

你现在查看的是最新测评结果

  • [2024-08-25 10:09:54]
  • 评测
  • 测评结果:TL
  • 用时:134ms
  • 内存:19008kb
  • [2024-08-25 10:09:53]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define ll long long
#define forn(i, n) for (ll i = 0; i < n; ++i)
#define forr(i, s, n) for (ll i = s; i < n; ++i)
#define fori(i, s, n) for (ll i = s; i > n; --i)
#define fora(i, n) for (auto i: n)
#define vi vector<int>
#define vll vector<ll>
#define prints(n) cout << (n) << " "
#define println(n) cout << (n) << "\n"

const int MOD = 998244353;
// const int MOD = 1e9 + 7;

void solve() {
    ll m, n, k; cin >> m >> n >> k;
    ll s, t; cin >> s >> t;

    vector<vector<pair<ll, ll>>> adj(n, vector<pair<ll, ll>>());

    map<pair<ll, ll>, ll> mp; 
    forn(i, m) {
        ll u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});

        mp[{u, v}] = i;
    }

    vector<set<pair<ll, ll>>> st(n, set<pair<ll, ll>>());
    forn(i, k) {
        ll a, b, c; cin >> a >> b >> c;
        st[b].insert({a, c});
    }

    // Tuple -Dist, Curr, Prev
    priority_queue<tuple<ll, ll, ll>> pq;
    pq.push({0, s, -1});

    ll ans = -1;
    vector<bool> visn(n), vise(m);
    while (!pq.empty()) {
        auto [dist, curr, prev] = pq.top(); pq.pop();
        // prints(dist); prints(curr); println(prev);

        if (curr == t) {
            ans = -dist; break;
        }

        if (visn[curr]) continue;
        visn[curr] = true;

        fora(edge, adj[curr]) {
            ll next = edge.first, cost = edge.second;

            if (visn[next]) continue;
            if (vise[mp[{curr, next}]]) continue;
            if (st[curr].find({prev, next}) != st[curr].end()) {
                visn[curr] = false; continue;
            }

            pq.push({dist - cost, next, curr});
        }
    }

    println(ans);
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    // cin >> t;
    while (t--) solve();

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3664kb

input:

9 7 3
3 2
6 3 2
3 0 3
0 1 12
1 0 4
1 2 2
1 5 4
4 1 8
5 4 7
5 2 5
0 1 2
4 1 5
1 5 2

output:

36

result:

ok single line: '36'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3504kb

input:

4 4 1
0 3
0 1 2
1 2 3
0 2 7
2 3 10
0 1 2

output:

17

result:

ok single line: '17'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

4 4 0
0 3
0 1 2
1 2 3
0 2 7
2 3 10

output:

15

result:

ok single line: '15'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

4 4 1
1 0
1 2 3
2 3 10
3 2 12
2 0 7
1 2 0

output:

32

result:

ok single line: '32'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

13 8 5
0 5
0 2 3
2 1 7
4 2 10
2 3 10
3 2 12
2 5 10
3 6 10
6 7 5
7 3 5
6 4 10
4 1 0
1 4 10
4 6 10
0 2 1
0 2 5
3 2 5
2 3 2
6 4 2

output:

63

result:

ok single line: '63'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

4 4 2
1 0
1 2 3
2 3 10
3 2 12
2 0 7
1 2 0
2 3 2

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

4 4 0
1 0
1 2 3
2 3 2
3 2 3
2 0 7

output:

10

result:

ok single line: '10'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

0 1 0
0 0

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 29ms
memory: 12268kb

input:

59996 30000 29997
0 29999
0 1 3
1 29999 7
1 2 1
2 1 1
2 3 1
3 2 1
3 4 1
4 3 1
4 5 1
5 4 1
5 6 1
6 5 1
6 7 1
7 6 1
7 8 1
8 7 1
8 9 1
9 8 1
9 10 1
10 9 1
10 11 1
11 10 1
11 12 1
12 11 1
12 13 1
13 12 1
13 14 1
14 13 1
14 15 1
15 14 1
15 16 1
16 15 1
16 17 1
17 16 1
17 18 1
18 17 1
18 19 1
19 18 1
19 2...

output:

60004

result:

ok single line: '60004'

Test #10:

score: 0
Accepted
time: 97ms
memory: 18240kb

input:

54776 10000 149059
0 9999
0 1168 720
0 7849 347
0 5301 937
0 1176 113
0 4762 833
0 6595 630
0 5846 548
0 528 878
1 3794 680
1 5036 171
1 4938 977
1 3180 522
1 9790 3
1 2139 221
1 3003 470
2 1054 534
2 5405 899
2 8279 740
2 1749 864
2 4634 773
2 7027 960
2 8151 321
2 4893 201
3 960 939
4 2349 671
5 6...

output:

2041

result:

ok single line: '2041'

Test #11:

score: 0
Accepted
time: 83ms
memory: 18412kb

input:

54727 10000 149795
0 9999
0 2611 51
0 6360 105
0 9596 66
0 7534 845
0 8007 758
0 1455 356
1 5761 949
1 5075 518
1 9029 436
1 432 235
1 4260 356
1 2845 870
1 5620 793
1 8169 483
2 4993 131
2 5942 50
2 3295 965
2 8977 538
3 8231 754
3 3852 321
3 3800 424
3 1731 493
4 5578 42
4 4697 337
4 3900 54
4 444...

output:

2572

result:

ok single line: '2572'

Test #12:

score: 0
Accepted
time: 134ms
memory: 19008kb

input:

55101 10000 151145
0 9999
0 8800 169
0 1752 969
1 6634 310
1 3693 284
1 1650 910
1 5991 323
1 2499 279
1 5189 154
1 4153 425
2 5566 738
2 2769 947
3 7442 71
3 4856 367
3 1109 398
3 6801 846
4 8109 118
4 290 414
4 315 259
4 4814 323
4 4821 135
5 2971 275
5 8576 605
6 7061 788
6 6608 336
6 1414 671
6 ...

output:

4445

result:

ok single line: '4445'

Test #13:

score: 0
Accepted
time: 113ms
memory: 18964kb

input:

54756 10000 150207
0 9999
0 1148 773
0 5763 985
0 2835 602
0 977 30
0 9223 600
0 2104 51
0 2094 617
1 4084 55
1 8160 512
1 2837 284
2 3303 473
2 9720 598
2 3700 191
2 9804 546
2 5114 882
2 7947 903
2 4817 499
3 5985 705
3 709 686
3 7579 496
3 172 434
3 7311 760
3 4812 52
4 609 174
5 1269 115
5 4314 ...

output:

3096

result:

ok single line: '3096'

Test #14:

score: 0
Accepted
time: 119ms
memory: 18760kb

input:

54656 10000 150741
0 9999
0 1511 252
0 7148 940
0 486 614
0 4770 773
0 2790 17
0 3626 76
0 9832 174
0 4562 827
1 5855 35
1 9290 513
1 2982 35
1 2854 751
1 6897 316
2 4990 733
2 5224 761
2 3283 21
3 6955 163
3 4823 213
3 2286 385
3 4033 965
4 9836 810
4 9699 309
5 1609 184
5 4014 366
6 6616 824
6 430...

output:

2876

result:

ok single line: '2876'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

6 5 1
1 0
1 2 3
2 3 10
3 2 12
2 0 7
3 4 20
4 0 30
1 2 0

output:

32

result:

ok single line: '32'

Test #16:

score: -100
Time Limit Exceeded

input:

54620 10000 148088
0 9999
0 8788 329
0 5514 152
0 8678 225
0 373 846
0 3314 720
0 8746 235
0 7183 822
0 6125 619
1 8172 190
2 4792 153
2 1637 513
2 8863 382
2 5682 160
2 1245 423
3 2635 430
3 7675 950
3 1297 203
3 7691 368
3 2102 619
3 4561 911
4 9702 137
4 3518 713
4 3199 10
5 6043 169
5 5485 427
5...

output:


result: