ACdream 1083 人民城管爱人民

拓扑排序，然后从终点开始递推。

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<iostream>

#include<ctime>

using namespace std;

typedef long long LL;

const double pi=acos(-1.0);

void File()

{

    freopen("D:\\in.txt","r",stdin);

    freopen("D:\\out.txt","w",stdout);

}

const int INF=0x7FFFFFFF;

int T,n,m;

struct Edge {int u,v,w,nx; } e[];

int sz,h[],r[];

struct X { int order,id; } p[];

int dis[][];

void add(int a,int b,int c)

{

    e[sz].u=a; e[sz].v=b; e[sz].w=c; e[sz].nx=h[a]; h[a]=sz++;

}

bool cmp(X a,X b){ return a.order>b.order; }

bool top()

{

    queue<int>Q; sz=;

    for(int i=;i<n;i++) if(r[i]==) Q.push(i);

    while(!Q.empty())

    {

        int t=Q.front(); Q.pop(); sz++; p[sz].order=sz; p[sz].id=t;

        for(int i=h[t];i!=-;i=e[i].nx)

            { r[e[i].v]--; if(r[e[i].v]==) Q.push(e[i].v); }

    }

}

int main()

{

    scanf("%d",&T); while(T--)

    {

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

        memset(h,-,sizeof h);

        memset(r,sz=,sizeof r);

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

        {

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

            add(u,v,w); r[v]++;

        }

        top();

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

        for(int i=n;i>=;i--)

        {

            int id=p[i].id;

            if(id==n-) { dis[id][]=dis[id][]=; continue;}

            for(int j=h[id];j!=-;j=e[j].nx)

            {

                if(dis[e[j].v][]==INF) continue;

                dis[id][]=min(dis[id][],dis[e[j].v][]+e[j].w);

            }

            int x1=INF,x2=INF;

            for(int j=h[id];j!=-;j=e[j].nx)

            {

                if(dis[e[j].v][]==INF) continue;

                x1=min(x1,dis[e[j].v][]+e[j].w);

            }

            bool flag=;

            for(int j=h[id];j!=-;j=e[j].nx)

            {

                if(dis[e[j].v][]==INF) continue;

                if(flag==&&dis[e[j].v][]+e[j].w==dis[id][]) { flag=; continue; }

                x2=min(x2,dis[e[j].v][]+e[j].w);

            }

            dis[id][]=max(x1,x2);

        }

        if(dis[][]==INF||dis[][]==INF) printf("-1\n");

        else printf("%d\n",dis[][]);

    }

    return ;

}