本文共 1131 字，大约阅读时间需要 3 分钟。

【题解】

显然这是个有向无环图的单源最短路问题，由于存在负权边，Dijkstra算法显然不适用，特殊 DAG 的性质使得 SPFA 算法无法在规定的时间限内求解出答案，Bellman-Ford算法显然不符合时间复杂度。（）

2≤n≤10^5，这显然是一个稀疏图，我们可以根据跑出来的拓扑排序求出最短路。

注意：如果两个人走完全程反而赚钱了那么消费作0处理.

【代码】

#define mem(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long int ll;const int maxn=1e5+5;const int INF=0x3f3f3f3f;struct node{    int next, to;    ll jffzr,cnz,c;}f[maxn<<1];int in[maxn],temp[maxn];int head[maxn];ll d[maxn];int n,m;ll Topo(int s) //拓扑排序{    queue 
   
     q;    for(int i=1;i<=n;i++)    {        d[i]=INF;        temp[i]=in[i];        if(!temp[i]) q.push(i); //找到入度为0的起始点    }    d[1]=0;    while(!q.empty())    {        int u=q.front(); q.pop();        for(int i=head[u];i!=-1;i=f[i].next)        {            int v=f[i].to;            d[v]=min(d[v],d[u]+f[i].c-(s==0?f[i].cnz:f[i].jffzr));             temp[v]--;            if(temp[v]==0) q.push(v);        }    }    return d[n]>0?d[n]:0; //没有花钱返回0}int main(){    int T; scanf("%d",&T);    while(T--)    {        scanf("%d%d",&n,&m);        mem(head,-1),mem(in,0);        for(int i=0;i
    
     s2) printf("rip!!!\n%lld\n",s1-s2);        else puts("oof!!!");    }}
    
   

转载地址：http://bfben.baihongyu.com/