这是一份 tarjin 求环的朱刘算法代码

#include<bits/stdc++.h>
using namespace std;
#define N 113
#define LL long long
#define INF 0x3f3f3f3f
int n,m,rt,pre[N],cnt,id[N];
bool vis[N],st[N];
LL ans,d[N][N],nd[N][N];
int tot,dfn[N],low[N],stk[N],tp;
void dfs(int u){
    vis[u]=true;
    for(int i=1;i<=n;++i)
        if(d[u][i]!=INF&&!vis[i]) dfs(i);
}
bool chk(){  //检查图是否连通
    memset(vis,0,sizeof vis);
    dfs(rt);
    for(int i=1;i<=n;++i)
        if(!vis[i]) return false;
    return true;
}
void taj(int u){  //tarjin求环并缩点
    dfn[u]=low[u]=++tot;
    stk[++tp]=u,st[u]=true;
    int v=pre[u];
    if(!dfn[v])
        taj(v),low[u]=min(low[u],low[v]);
    else if(st[v])
        low[u]=min(low[u],dfn[v]);
    if(low[u]==dfn[u]){
        cnt++;int y;
        do{y=stk[tp--],st[y]=false,id[y]=cnt;}
        while(y!=u);
    }
}
int main(){
	scanf("%d%d%d",&n,&m,&rt);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j) d[i][j]=INF;
    for(int i=1;i<=m;++i){
    	int u,v;LL w;
        scanf("%d%d%lld",&u,&v,&w);
        if(u!=v&&v!=rt) d[u][v]=min(d[u][v],w);
	}
    if(!chk()) return (puts("-1"),0);
    while(1){  //朱刘算法主体
        for(int i=1;i<=n;++i){
            pre[i]=i;
            for(int j=1;j<=n;++j)
                if(d[j][i]<d[pre[i]][i])
                    pre[i]=j;
        }
        memset(dfn,0,sizeof dfn);
        tot=cnt=0;
        for(int i=1;i<=n;++i)
            if(!dfn[i]) taj(i);
        rt=id[rt];  //*1
        if(cnt==n){
            for(int i=1;i<=n;++i)
                ans+=d[pre[i]][i];  //*2
            break;
        }
        for(int i=1;i<=n;++i)
            if(id[pre[i]]==id[i])
                ans+=d[pre[i]][i];  //*3
        for(int i=1;i<=cnt;++i)
            for(int j=1;j<=cnt;++j)
                nd[i][j]=INF;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                if(d[i][j]!=INF&&id[i]!=id[j]){
                    int a=id[i],b=id[j];
                    if(id[pre[j]]==id[j]) nd[a][b]=min(nd[a][b],d[i][j]-d[pre[j]][j]);
                    else nd[a][b]=min(nd[a][b],d[i][j]);
                }
        n=cnt,memcpy(d,nd,sizeof d);
    }
    printf("%lld\n",ans%INF);  //*4
    return 0;
}

最开始建的图的时候判断 if(u!=v&&v!=rt) d[u][v]=min(d[u][v],w); 也就是如果这条边的终点为根那么将其忽略（因为答案中肯定不会有指向根的边）。

标有 *1 那行的代码将 rt 转为 id[rt]，因为本来在 *2 *3 处有 i!=rt 的判断，也就是当枚举到的点为根时不统计答案，因为没有边指向根，d[pre[i]][i] 的结果肯定是 INF。

现在的问题是我在任何一处加上判断，最终答案都不对，反而不加判断然后在最终结果上 %INF 过掉了（如果不加判断的话那么 *1 处实际是没有用的）。

于是尝试去掉 *1 处，在后两处加上判断，答案仍然不对。

于是我心中有无穷的问号。到底是我代码哪个部分出问题了，还是实际上就是这么个运行过程。