0

This is my code. It is for solving single-source shortest path problem using Dijkstra algorithm.

#include <cstdio>
using namespace std;

int mp[2505][2505];
int n, m, s, t;
const int INF = INT_MAX/4;

int main()
{
    // freopen(".\\IO\\stdin.in", "r", stdin);

    for (int i=0; i<2505; i++)
        for (int j=0; j<2505; j++)
            mp[i][j] = i==j ? 0 : INF;
    
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i=0; i<m; i++)
    {
        int u, v, t;
        scanf("%d%d%d", &u, &v, &t);
        mp[u][v] = mp[v][u] = t;
    }

    int dis[3000];
    for (int i=1; i<=n; i++)
        dis[i] = INF;
    dis[s] = 0;

    bool walked[2505];
    memset(walked, 0, sizeof(walked));
    for (int i=1; i<=n; i++)
    {
        int minN = -1, minV = INF;
        for (int j=1; j<=n; j++)
        {
            if (walked[j]) continue;
            if (dis[j] < minV)
                minV=dis[j], minN=j;
        }

        for (int p=1; p<=n; p++)
            if (dis[minN] + mp[minN][p] < dis[p])
                dis[p] = dis[minN] + mp[minN][p];
        walked[minN] = 1;
    }

    printf("%d\n", dis[t]);
    return 0;
}

I tried to paste the input data in console, and got the right answer 1559.
But when I wrote freopen(".\\IO\\stdin.in", "r", stdin); (just like the annotation at the beginning of the main()), put the data in the correct file and runs the program, it prints 0.

Input data has 6000+ lines, so I put it at ubuntu pastebin. https://pastebin.ubuntu.com/p/7WhKQW2pZj/

Other info:
Windows 10
Complie command: g++ a.cpp -o a.exe -Wall
C++ standard: C++11

EchoInVoid
  • 9
  • 1
  • 2
    `C++ standard: C++11` -- Nothing in your code deals specifically with C++11. Except for that non-standard header `#include `, your entire code is `C`. – PaulMcKenzie Apr 02 '23 at 13:45
  • 1
    Does `freopen` return a valid stream, or does it return NULL? – paddy Apr 02 '23 at 13:45
  • 1
    [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) | [Why should I not `#include `?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) | [Why is `using namespace std;` considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – Evg Apr 02 '23 at 13:47
  • It returns a valid stream. Magically, when I wrote `if (freopen(".\\IO\\stdin.in", "r", stdin) != NULL) printf("NOT\n");`, the program gave the correct answer and 'NOT'. – EchoInVoid Apr 02 '23 at 13:49
  • Could be array out of bounds somewhere. Looking at `dis[minN]` what guarantee is there that `minN` is not `-1`? – john Apr 02 '23 at 13:50
  • @EchoInVoid *Magically, ...* Seems like classic undefined behaviour. I think you probably have an array out of bounds access. – john Apr 02 '23 at 13:50
  • @EchoInVoid For laughs replace your arrays with vectors and replace `[]` with `at`. That way if there is an out of bounds access you will know about it. – john Apr 02 '23 at 13:52
  • If you had used `std::vector` instead of those gigantic arrays, and then used `push_back` to add the data to those vectors, then it would be very easy to detect an out-of-bounds condition by using the `at()` function. This is why trying to learn actual C++ from competition websites is a waste of time. – PaulMcKenzie Apr 02 '23 at 13:52
  • The debugger doesn't work well (and I couldn't use it well) on my machine. I'm an OIer, so I am used to using bits/stdc++.h and 'using namespace std;'. If this annoys you, I felt sorry for that. – EchoInVoid Apr 02 '23 at 13:52
  • @EchoInVoid -- I am using Visual Studio. That header is not accepted by that compiler, as it is non-standard. Why not simply use the correct header files, so that others can actually compile the code and run it? – PaulMcKenzie Apr 02 '23 at 13:53
  • Thank you all the guys! There is an array out of bounds. When I replaced `int minN = -1` with `int minN = i`, problem solved! – EchoInVoid Apr 02 '23 at 13:57
  • @PaulMcKenzie In Chinese OIs, we usually use `bits/stdc++.h`. This can save a lot of time looking for the right header. I know that's bad in large projects, but I think it's useful in competitions. If that annoys you, I felt sorry. – EchoInVoid Apr 02 '23 at 13:59
  • 1
    *If that annoys you* -- You are supposed to post code that others can compile and help *you* with it. Here is the change: `#include `. Is it that hard to simply have that? This is not a competition site -- there is no competition going on here, just people trying to help you. – PaulMcKenzie Apr 02 '23 at 14:02
  • @PaulMcKenzie Actually, almost everyone around me recommended to use `bits/stdc++.h` when in competitions. Because in large competitions, the compile environment is wrote in the docs. These competitions usually use g++ which allows `bits/stdc++.h`. As OIers, we write like this to save time sometimes. – EchoInVoid Apr 02 '23 at 14:06
  • @PaulMcKenzie Okay. I've been in this website for a short time. So I didn't know that. I will edit the question now. Thank you! – EchoInVoid Apr 02 '23 at 14:08
  • 1
    @EchoInVoid -- The problem with using that header, even for competitions, is that the code you write may not compile using that header or behave differently because of that header. For example, if you write a `swap` function, which `swap` function is going to be actually called, your `swap` function, or `std::swap`? If you have a `gcd` function, which `gcd` function is going to be called, yours or `std::gcd`? This is also why `using namespace std;` is dangerous. So you will lose the competition because you are stuck on a compiler error, or your code is doing strange things. – PaulMcKenzie Apr 02 '23 at 14:11

0 Answers0