P1807 最长路_NOI导刊2010提高（07）

题目描述

设G为有n个顶点的有向无环图，G中各顶点的编号为1到n，且当为G中的一条边时有i < j。设w（i，j）为边的长度，请设计算法，计算图G中<1，n>间的最长路径。

输入输出格式

输入格式：

输入文件longest.in的第一行有两个整数n和m,表示有n个顶点和m条边，接下来m行中每行输入3个整数a，b，v（表示从a点到b点有条边，边的长度为v）。

输出格式：

输出文件longest.out，一个整数，即1到n之间的最长路径.如果1到n之间没连通，输出-1。

输入输出样例

输入样例#1：

2 1

1 2 1

输出样例#1：

说明

20%的数据，n≤100，m≤1000

40%的数据，n≤1,000，m≤10000

100%的数据，n≤1,500，m≤50000，最长路径不大于10^9

Solution:

本题裸的最短路，直接将dis数组初始赋值为-inf，将三角不等式改为dis[v]<dis[u]+val[u]，最后输出时判断下-1的情况就ok了。

代码：

#include<bits/stdc++.h>

#define il inline

#define ll long long

#define debug printf("%d %s\n",__LINE__,__FUNCTION__)

using namespace std;

const int N=,inf=-;

int n,m,h[N],to[N],net[N],cnt,dis[N],val[N];

bool vis[N];

il int gi()

{

    int a=;char x=getchar();bool f;

    while((x<''||x>'')&&x!='-')x=getchar();

    if(x=='-')x=getchar(),f=;

    while(x>=''&&x<='')a=a*+x-,x=getchar();

    return f?-a:a;

}

il void add(int u,int v,int w)

{

    to[++cnt]=v,net[cnt]=h[u],val[cnt]=w,h[u]=cnt;

}

il void spfa()

{

    queue<int>q;

    for(int i=;i<=n;i++)dis[i]=inf;

    dis[]=;vis[]=;q.push();

    while(!q.empty())

    {

        int u=q.front();q.pop();vis[u]=;

        for(int i=h[u];i;i=net[i])

        if(dis[to[i]]<dis[u]+val[i]){

            dis[to[i]]=dis[u]+val[i];

            if(!vis[to[i]])q.push(to[i]),vis[to[i]]=;

        }

    }

}

int main()

{

//    n=gi(),m=gi();

    scanf("%d%d",&n,&m);

    int u,v,w;

    for(int i=;i<=m;i++){

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w);

    }

    spfa();

    printf("%d",dis[n]==inf?-:dis[n]);

    return ;

}

巴特西

P1807 最长路_NOI导刊2010提高（07）

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章