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

· · 题解

题目链接

思路点播：

数据结构：用结构体e保存每一条边，d[i]表示从1到i的最长路，v[i]==true则表示i号节点在队列q中，v[i]==false则表示不在，b[i]==true则表示1可以到达i，b[i]==false则表示1不能到达i

算法过程：

1、读入数据，并储存每一条边

const int N=1510,M=50100;
struct node{
    int next,to,len;
}e[M];int head[N],cnt;
void add_node_edge(int x,int y,int z){
    e[++cnt]=(node){head[x],y,z};head[x]=cnt;
}
int main(){
    n=read();m=read();
    for(i=1;i<=m;i++){
        x=read();y=read();z=read();
        add_node_edge(x,y,z);
        //若题目为无向图，则再加一句：
        //add_node_edge(y,x,z)
    }
}

其中，read()函数为读入优化（听说每500万个数据可省100ms）

#define g(c) isdigit(c)
#define gc getchar()
inline int read(){
    char c=0;int x=0,f=0;
    while (!g(c)) f|=c=='-',c=gc;
    while (g(c)) x=x*10+c-48,c=gc;
    return f?-x:x;
}
//需要调用cctype库

2、套用spfa算法

queue<int> q;bool v[N],b[N];
inline void spfa_algorithm(){
    memset(d,0,sizeof(d));
    memset(v,1,sizeof(v));
    memset(b,0,sizeof(b));
    q.push(1);v[1]=false;b[1]=1;
    //1号节点可以到达
    while (q.size()){
        int z=q.front();q.pop();v[z]=1;
        for(int i=head[z];i;i=e[i].next){
            register int u=e[i].to;
            if (d[u]<d[z]+e[i].len){
                d[u]=d[z]+e[i].len;b[u]=1;
                //u号节点被扩展到说明它可以到达
                if (v[u]){
                    q.push(u);v[u]=false;
                }
            }
        }
    }
}

3、根据b[n]和d[n]的值输出

if (b[n]==0) printf("-1");//n号节点无法到达，输出-1
else printf("%d",d[n]);//n号节点可以到达，输出最长路

评测记录：

状态/分数：Accepted，100分

语言/长度：C++，1.21KB

耗时/内存：57ms，1552KB

#include <bits/stdc++.h>
using namespace std;
const int N=1510,M=50100;
struct node{
    int next,to,len;
}e[M];int head[N],cnt;
void add_node_edge(int x,int y,int z){
    e[++cnt]=(node){head[x],y,z};head[x]=cnt;
}
int d[N],n,m,i,x,y,z;
#define g(c) isdigit(c)
#define gc getchar()
inline int read(){
    char c=0;int x=0,f=0;
    while (!g(c)) f|=c=='-',c=gc;
    while (g(c)) x=x*10+c-48,c=gc;
    return f?-x:x;
}
queue<int> q;bool v[N],b[N];
inline void spfa_algorithm(){
    memset(d,0,sizeof(d));
    memset(v,1,sizeof(v));
    memset(b,0,sizeof(b));
    q.push(1);v[1]=false;b[1]=1;
    while (q.size()){
        int z=q.front();q.pop();v[z]=1;
        for(int i=head[z];i;i=e[i].next){
            register int u=e[i].to;
            if (d[u]<d[z]+e[i].len){
                d[u]=d[z]+e[i].len;b[u]=1;
                if (v[u]){
                    q.push(u);v[u]=false;
                }
            }
        }
    }
}
int main(){
    n=read();m=read();
    for(i=1;i<=m;i++){
        x=read();y=read();z=read();
        add_node_edge(x,y,z);
    }
    spfa_algorithm();
    if (b[n]==0) printf("-1");
    else printf("%d",d[n]);
    return 0;
}

最后，说一下万能头bits/stdc++.h

noi比赛文件中说：理论上可以用万能头，但实际中可能不支持使用万能头，若因为使用万能头而导致CE（编译错误），比赛概不负责，即选手负全责！！！

所以，比赛时建议不要使用万能头，平时可以稍微使用一下