题解：

之前知道正解并没有写过。。

#include 
      
       using namespace std;#define rint register int#define IL inline#define rep(i,h,t) for (int i=h;i<=t;i++)#define dep(i,t,h) for (int i=t;i>=h;i--)#define me(x) memset(x,0,sizeof(x))char ss[1<<24],*A=ss,*B=ss;IL char gc(){  return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++;}template
       
        void read(T &x){  rint f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=(c^48);  while (c=gc(),c>47&&c<58) x=(x<<3)+(x<<1)+(c^48); x*=f;}const int N=3e5;struct re{  int a,b,c;}e[N],jl[N];int n,m,k,p,head[N],l,rd[N],tim[N];void arr(int x,int y,int z){  e[++l].a=head[x];  e[l].b=y;  e[l].c=z;  head[x]=l;}queue
        
          q;stack
         
           S;int dfn[N],low[N],col[N],color_cnt,sz[N],cnt,tim2[N];bool ins[N];void tarjan(int x,int y){  dfn[x]=low[x]=++cnt; S.push(x); ins[x]=1;  for (rint u=head[x];u;u=e[u].a)  {    rint v=e[u].b;      if (!dfn[v])      {        tarjan(v,x);        dfn[x]=min(dfn[x],low[v]);      }      if (ins[v]) dfn[x]=min(dfn[x],dfn[v]);  }  if (dfn[x]==low[x])  {    color_cnt++;    while (1)     {      int y=S.top(); S.pop(); col[y]=color_cnt; ins[y]=0; sz[color_cnt]++;      if (y==x) break;    }  }}const int INF=5e8;int dis[N],dis1[N],dis2[N];struct cmp{  bool operator () (re x,re y)  {    return x.b>y.b;  }};priority_queue
          
           
            ,cmp> Q;bool vis[N];void dij(int x){ me(vis); rep(i,1,n) dis[i]=INF; Q.push((re){x,0}); dis[x]=0; while (!Q.empty()) { int x=Q.top().a; Q.pop(); if (vis[x]) continue; vis[x]=1; for (rint u=head[x];u;u=e[u].a) { int v=e[u].b; if (dis[v]>dis[x]+e[u].c) { dis[v]=dis[x]+e[u].c; Q.push((re){v,dis[v]}); } } }}int f[N][52];const int N2=1.5e7;re ve[N2];IL void js(int &x,int y){ x=(x+y)%p;}bool cmp3(re y,re x){ int jl1=dis1[x.a]+x.b; int jl2=dis1[y.a]+y.b; return (jl2
            
             
              1) tt=1; if (tt) { cout<<-1<
             
            
           
          
         
        
       
      

我觉得这细节真的挺多的。。

而且我都不知道我去年怎么写的60分了。。

网上的方法好像比我的简单。。。

首先在0环上我的处理是

先缩点，然后判缩完后的点能否在路径上

如果能在，输出-1

由于这个缩点还是带来了比较大的干扰。。

调试中的几个错都是这个产生的。。

另外最短路据说是线段树优化跑的最快？？

最后的dp还是比较简单的

f[i][j]表示到i点，比原先最短路长j，然后对终点跑一遍最短路来剪枝

然后发现相同dis可以互相转移

所以根据零边拓扑排序一下

网上的判0环的方法比较简单

直接在做的时候 如果扩展到之前的状态 就说明有0环

这很显然啊。。。。

主要刚开始没仔细想这个过程。。

noip至少得留1:30 才能搞完这题吧。。 2:00就比较稳

诶网上最简单的代码好简单啊。。。

直接对s跑一遍最短路，然后直接dp 省掉所有过程啊 而且还挺快的。。。（看来这个剪枝作用也不是很大）

 所以下次还是想清楚再写。。。 看看有没有简单的办法

要是写后面这份代码 1小时足够了啊。。。