DIJ不能跑最长路！！

首先，这道题的做法我不再进行叙述，只是说一下为什么很多人打的（认为是）dij最长路但是wa掉而转spfa。

（太菜了第一遍没有注意到）

priority_queue<pa, vector<pa>, greater<pa> > q;
il void DIJ(int s)
{
    for(int i = 1; i <= num; ++i) dis[i] = -INF, v[i] = 0;
    dis[s] = val[s]; q.push(m_p(0, s));
    while(q.size())
    {
        int x = q.top().second; q.pop();
        if(v[x]) continue;
        v[x] = 1;
        for_edge(i, x)
        {
            int y = ver[i];
            if(dis[y] < dis[x] + val[y])
            {
                dis[y] = dis[x] + val[y];
                q.push(m_p(dis[y], y));
            }
        }
    }
}

首先我们先来看为什么81分

注意这个代码只是对于最短路的代码稍微改了一下，但是我们注意到我们的堆还是小根堆啊喂（很震惊为什么这么高的分）。

然后把小根堆改了之后发现这么一个事，它还是wa了两个点87pts

il void DIJ(int s)
{
    for(int i = 1; i <= num; ++i) dis[i] = -INF, v[i] = 0;
    dis[s] = val[s]; q.push(m_p(0, s));
    while(q.size())
    {
        int x = q.top().second; q.pop();
        if(v[x]) continue;
        v[x] = 1;
        for_edge(i, x)
        {
            int y = ver[i];
            if(dis[y] < dis[x] + val[y])
            {
                dis[y] = dis[x] + val[y];
                q.push(m_p(dis[y], y));
            }
        }
    }
}

我们再次对我们的代码进行仔细分析，因为我们的vis标记是对于我们之前的贪心而加上的优化，这时候就会造成答案的错误，所以我们并不需要vis数组了。。然鹅没有vis会T

举个例子吧 （丑的一批，但是能说明问题。。） 我们进行模拟一下，从1号点开始，我们第一轮会把2,4两个点加进来，而因为我们的大根堆存在，所以4点先跑，而此时4被标记，而显然不是最优的策略。

因此我们的问题就分析完了，得到了这样的代码

il void DIJ(int s)
{
    for(int i = 1; i <= num; ++i) dis[i] = -INF;
    memset(v, 0, sizeof(v));
    dis[s] = val[s]; q.push(m_p(0, s));
    while(q.size())
    {
        int x = q.top().second; q.pop();
        for_edge(i, x)
        {
            int y = ver[i];
            if(dis[y] < dis[x] + val[y])
            {
                dis[y] = dis[x] + val[y];
                q.push(m_p(dis[y], y));
            }
        }
    }
}

这样我们不可避免的会T掉第三个点，（没有vis当然慢的一批）所以我们的dij就不能保证时间复杂度，所以最长路不要用dij了。他已经变质了。

如有错误，请指出。毕竟我菜的一批

仅告诫后人不要再犯这样的错误，直接奔向spfa，虽然他死了（让它诈尸吧）