题解 | #【模板】单源最短路1#为什么朴素迪杰斯特拉只能过60%，剩下的显示答案错误，为什么？

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
#define endl '\n'
// #define int long long
const int INF = 0x7FFFFFFF;                // 2147483647
const long long LLNf = 0xFFFFFFFFFFFFFFFF; // 18446744073709551615;
const int mod = 1e9 + 7;
const int MOD = 998244353;
const int N = 5000+ 10;
int Map[N][N],dis[N];
bool vis[N];
void solve()
{
    int n, m,minn;
    cin >> n >> m;
    for (int i = 0; i < n;i++)
    {
        vis[i] = 0;
        dis[i] = INF;
        for (int j = 0;j<n;j++)
        {
            Map[i][j] = INF;
        }
    }
    while(m--)
    {
        int u, v;
        cin >> u >> v;
        u--,v--;
        Map[u][v] = 1;
        Map[v][u] = 1;
    }
    int now = 1, target = n,next;
    now--,target--;
    dis[now] = 0;
    vis[now] = 1;
    while(now!=target)
    {
        minn = INF;
        for (int i = 0; i < n;i++)
        {
            if(Map[now][i]!=INF)
            {
                dis[i] = min(dis[i], dis[now] + Map[now][i]);
            }
            if(!vis[i]&&minn>dis[i])
            {
                next = i;
                minn = dis[i];
            }
        }
        if(minn==INF)
            break;
        now = next;
        vis[now] = 1;
    }
    if(dis[target]==INF)
        cout << -1 << endl;
    else
        cout << dis[target] << endl;
}
    

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}