题解 P1807 【最长路_NOI导刊2010提高（07）】

· · 题解

C++的第二篇题解

这道题我是用BFS做的，自我感觉良好除了有几个小问题。

首先这是求最长路（异常微妙）

然后我发现这题的数据是有点大的要加一点优化。

如果现在的头指针已经到N了，其实也没有必要往下做了，而且肯定也不会有情况往下做了因为边 <i,j> i是必定小于j的。

再其次这个值可能会重复多次，就会占用很大的时间效率和空间（毕竟这是个队列）所以要用数组存一下，这个点的最大值，如果从头指针到这个值，还没有原先到这个值大，那么它一定不会是最优解。

注意完问题后，码一个约等于裸的BFS就奇奇妙妙的A了。

#include <cstdio>
#include <cmath>//我是一个新手，学习C++从头文件做起

using namespace std;

int a[1510][1510];
int b[1510][1510];
int ans=-1;
int h[15050000];
int hh[15050000];//队列h存下标，hh存值
int bo[1510];

int max(int x,int y){
    return x>y?x:y;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        a[x][0]++;
        a[x][a[x][0]]=y;//邻接表式存储，a存这条边到的位置，b存这条边的长度
        b[x][a[x][0]]=z;
    } 
    int hard=1,tail=1;
    h[hard]=1;
    hh[1]=0;
    while (hard<=tail){//BFS裸的！！
        if (h[hard]==n){//到N了就判断，找最优解
            ans=max(ans,hh[hard]);
        } else {//不然的话就继续扩展
        int x=h[hard];
        for (int i=1;i<=a[x][0];i++){
            if (bo[a[x][i]]<hh[hard]+b[x][i]){
                tail++;
                h[tail]=a[x][i];
                hh[tail]=hh[hard]+b[x][i];
                bo[a[x][i]]=hh[tail];
            }
        }
        }
        hard++;
    }
    printf("%d",ans);//输出
}

代码丑陋，请见谅

第二次提交C++题解希望通过