Rockdu's Blog

题目描述

设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。

输入输出样例

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

        在洛谷跳题，很高兴的就水了一个SPFA交上去。没什么坑，轻松+愉快。

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1500+100;
const int maxm=50000+100;
int n,m;
struct edge{
    int v,w,next;
}e[maxm];
int cnt;
int head[maxn];
int vis[maxn];
int dis[maxn];

void adde(int u,int v,int w){
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt++;
}

int spfa(){
    memset(dis,-1,sizeof(dis));
    queue<int > q;
    q.push(1);
    vis[1]=1,dis[1]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop(),vis[u]=0;
        for(int i=head[u];i!=-1;i=e[i].next){
            int v=e[i].v;
            if(dis[u]+e[i].w>dis[v]){
                dis[v]=dis[u]+e[i].w;
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return dis[n];
}

int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        adde(u,v,w);
    }
    printf("%d\n",spfa());
    return 0;
}