一个有关SPFA初始化的问题
  • 板块P1807 最长路
  • 楼主Merron
  • 当前回复6
  • 已保存回复6
  • 发布时间2020/8/10 11:43
  • 上次更新2023/11/6 20:46:27
查看原帖
一个有关SPFA初始化的问题
338370
Merron楼主2020/8/10 11:43

这是我原来的代码:

#include <bits/stdc++.h>
#define M 50050
#define N 1550
using namespace std ;

int n, m ;
int cnt = 0 ;
long long ans ;

struct edge
{
    int frm, dis, to ;
} ;

edge E[M] ;
int head [N] ;
int dis [N] ;
bool vis [N] ;

deque<int> q ;

void Add_edge (int frm, int to, int dis)
{
    cnt ++ ;
    E[cnt].frm = head[frm] ;
    E[cnt].to = to ;
    E[cnt].dis =  dis ;
    head[frm] = cnt ;
}

void SPFA()
{
    memset (dis, -10000000, sizeof(dis)) ;
    dis[1] = 0 ;
    vis[1] = 1 ;
    q.push_back(1) ;

    while (!q.empty ())
    {
        int x = q.front () ;
        q.pop_front () ;
        for (int i = head[x] ; i != 0 ;i = E[i].frm)
        {
            int y = E[i].to ;
            if (dis[y] < dis[x] + E[i].dis)
            {
                dis[y] = dis[x] + E[i].dis ;
                if (!vis[y])
                {
                    vis[y] = 1 ;
                    if (!q.empty())
                    {
                        if (dis[y] < dis[q.front()])
                        {
                            q.push_back(y) ;
                        }
                        else
                        {
                            q.push_front(y) ;
                        }
                    }
                    else
                    {
                        q.push_back(y) ;
                    }
                }
            }
        }
        vis[x] = 0;
    }
}

int main ()
{
    cin >> n >> m ;
    for (int i = 1 ;i <= m ;i ++)
    {
        int frm, to, dis ;
        cin >> frm >> to >> dis ;
        Add_edge (frm, to, dis) ;
    }
    SPFA() ;
    if (dis[n] == -10000000)
    {
        cout << -1 << endl ;
    }
    else
    {
        cout << dis[n] << endl ;
    }
    return 0 ;
}

这代码没有什么问题, 但是

看看这几组组数据:

数据1:

Input :
3 1
1 2 31
The right anwser :
-1
My answer :
-2139062144

数据2:

Input :
2 0
The right anwser :
-1
My answer :
-2139062144

为什么每次都是 -2139062144??? 于是我将代码对dis的初始化数值改成了 -2139062144 居然全部AC

请问为什么会这样? -2139062144这个数有什么特殊性?

2020/8/10 11:43
加载中...