ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1930. Ivan's Car

Still WA #11 ?
Posted by Hikmat Ahmedov 26 Jan 2013 00:38
This test helped me to find my bug. I modified dijkstra algo and added direction array.
9 12
7 3
9 3
9 2
1 2
1 3
4 7
4 1
5 1
4 8
5 8
6 5
2 6
1 8
Answer:0


Edited by author 31.01.2013 17:37
Re: Still WA #11 ?
Posted by raven 4 Aug 2013 20:04
Thank you
Re: Still WA #11 ?
Posted by Akshat Shah 5 May 2020 22:28
Thanks a lot! I was maintaining an array how[], which was storing how to get at that node (uphill mode or downhill node). But that failed Test case #11. I modified the code such that I start Dijkstra's algorithm at the destination node (Orlov's city) as the source node and Ivan's city as the target node. I actually interchanged source with end. So now I think my how[] array stores how one should get here. And it passed all test cases! Does this work because we have no limitation on how to start, but rather how we end makes more impact on the solution? I cannot derive a formal proof. Any comments are welcome
Re: Still WA #11 ?
Posted by Mac Phuc Khang 16 Aug 2023 16:30
You have to use 2d array to have 2 min costs from s to t with 2 states 0 (up) and 1 (down) (dis[u][0], dis[u][1]), if you just you 1d array and AC, it must be lucky.

This is my AC code run in 0.031s:
((const) inf = 1e9,
(define) ep = emplace (= push/insert),
(define) eb = emplace_back (= push_back),
ep and eb both are faster than push and push_back,
emplace_front/emplace/emplace_back = push_front/(push/insert)/push_back but faster because it doesn't copy then moves value into array, it pushes directly into array)

#pragma GCC optimize( "Ofast" )
#pragma GCC target( "avx2", "sse4.2", "abm", "bmi", "bmi2", "fma", "mmx", "popcnt", "lzcnt" )

#include <bits/stdc++.h>

#define endl '\n'
#define inf 1e18
#define int long long
#define pii pair <int, int>
#define vii vector <pii>
#define tiii tuple <int, int, int>
#define viii vector <tiii>
#define ep emplace
#define eb emplace_back

using namespace std;

const int MaxN = 1e4 + 10;

int n, m, s, t, f[MaxN][2];
vii a[MaxN];
priority_queue <tiii, viii, greater <tiii>> pq;

signed main()
{
    cin.tie(0) -> sync_with_stdio(0);
    __builtin_ia32_ldmxcsr ( 40896 );

    fill(&f[0][0], &f[0][0] + sizeof(f) / sizeof(f[0][0]), inf);

    cin >> n >> m;
    for (int u, v, i = 1; i <= m; ++i)
    {
        cin >> u >> v;
        a[u].eb(v, 0);
        a[v].eb(u, 1);
    }
    cin >> s >> t;

    f[s][0] = f[s][1] = 0;
    pq.ep(f[s][0], s, 0);
    pq.ep(f[s][1], s, 1);
    while (!pq.empty())
    {
        auto [x, u, y] = pq.top(); pq.pop();
        if (x > f[u][y]) continue;
        if (u == t) break;
        for (auto [v, z] : a[u])
        {
            int w = f[u][y] + (y != z);
            if (f[v][z] > w)
                pq.ep(f[v][z] = w, v, z);
        }
    }

    cout << min(f[t][0], f[t][1]) << endl;
}

if you have any question, you can ask me :))