本人代码有一点抽象

有没有大佬啊，没有程序拿来对拍，没有测试数据，真没救了……

网址：link

题意简述：给定一个有向图以及源点，对于每一个节点，如果源点与它不连通，输出"*"；如果源点到这个节点最短路长度为负无穷，则输出“-”；否则，输出源点到这个节点的长度。

本人思路：强连通分量 + spfa判负环

#include<bits/stdc++.h>
using namespace std;
#define int long long

namespace FastIO
{
	const int Mt = 1e5;
	inline char getch()
	{
		static char buf[Mt],*p1 = buf,*p2 = buf;
		return p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,Mt,stdin),p1 == p2) ? EOF : *p1++;
	}
	
	inline int input()
	{
		int num = 0,f = 1;
		char ch = getch();
		while(ch < '0' || ch > '9')
		{
			if(ch == '-') f = -1;
			ch = getch();
		}
		while(ch >= '0' && ch <= '9')
		{
			num = (num << 1) + (num << 3) + (ch ^ 48);
			ch = getch();
		}
		return num * f;
	}
	
	inline void printNum(int num)
	{
		if(num >= 10) printNum(num / 10);
		putchar(num % 10 + 48);
	}
	
	inline void print(int num,char ch = ' ')
	{
		if(num < 0) putchar('-'),num = -num;
		printNum(num);
		putchar(ch);
	}
}
using FastIO::input;
using FastIO::print;

const int N = 5005;
struct Node { int v,w; };
int n,m,s,ts,top,cnt;
int dfn[N],low[N],st[N],bel[N],ele[N],dis[N],num[N],ext[N];
//dfn -> dfn序，low -> low，st -> s栈，bel -> 每一个节点所属强连通分量编号
//ele -> 每一个强连通分量之中的一个元素,dis -> 最短路距离,num -> 松弛次数
//ext -> 强连通分量大小 
bitset <N> cst,flag; 
// cst -> 是否存在于栈中,flag -> 是否到达这个强连通分量的最短路为负无穷 
vector <int> vimg[N];//缩点后的图 
vector <Node> edge[N];//原图 
queue <int> q;//spfa的queue 

void Tarjan(int u)//标准tarjan 
{
	dfn[u] = low[u] = ++ts;
	st[++top] = u,cst[u] = 1;
	
	for(auto tmp : edge[u])
	{
		int v = tmp.v;
		if(!dfn[v])
		{
			Tarjan(v);
			low[u] = min(low[u],low[v]);
		}
		else if(cst[v]) low[u] = min(low[u],dfn[v]);
	}
	
	int node; 
	if(dfn[u] == low[u])
	{
		cnt++,ele[cnt] = u,ext[cnt] = 1;
		//ele记录每一个强连通分量的其中一个点作为spfa出发点 
		do node = st[top--],cst[node] = 0,bel[node] = cnt,ext[cnt]++;
		while(node != u);
	}
}

void add(int u) //add建立缩点之后的图 
{
	for(auto tmp : edge[u])
	{
		int v = tmp.v;
		if(bel[u] != bel[v])
			vimg[bel[u]].push_back(bel[v]);
	}
}

void spread(int id)
//如果一个强连通分量是不合法的，那么它连向的强连通分量均不合法 
{
	for(int v : vimg[id])
	{
		if(!flag[v])
		{
			flag[v] = 1;
			spread(v);
		}
	}
}

void Spfa(int id,int mod)
// mod = 0是判负环，mod = 1跑最短路 
{	
	if(!mod & flag[id]) //如果已经不合法，直接spread然后返回 
	{
		spread(id);
		return;
	}
	
	int u = ele[id];
	if(mod) u = s;
	bitset <N> vis;
	while(!q.empty()) q.pop();
	memset(dis,0x3f,sizeof dis);
	memset(num,0,sizeof num);
	dis[u] = 0,vis[u] = 1;
	q.push(u);
	
	while(!q.empty())
	{
		u = q.front(); q.pop();
		vis[u] = 0;
		for(auto tmp : edge[u])
		{
			int v = tmp.v,w = tmp.w;
			
			if(!mod) 
			{
				if(id != bel[v]) continue;
			}
			else if(flag[bel[v]]) continue;
			
			if(dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				if(!vis[v])
				{
					if(++num[v] >= ext[id]) flag[id] = 1;
					vis[v] = 1,q.push(v);
				}
			}
		}
		if(flag[id]) break;
	}
	
	if(!mod & flag[id]) spread(id); // 如果不合法，spread 
}

signed main()
{
	freopen("path.in","r",stdin);
	freopen("path.out","w",stdout); 
	n = input(),m = input(),s = input();
	for(int i = 1;i <= m;i++)
	{
		int u = input(),v = input(),w = input();
		edge[u].push_back({v,w});
	}
	Tarjan(s);
	
	for(int i = 1;i <= n;i++)	
		add(i);
	
	for(int i = 1;i <= cnt;i++)
		Spfa(i,0);
		
	Spfa(s,1);
	
	for(int i = 1;i <= n;i++)
	{
		if(!dfn[i]) puts("*");//没有dfn序说明不连通 
		else if(flag[bel[i]]) puts("-");//被标记为不合法 
		else print(dis[i],'\n');//最短路 
	}
}

/*
2 1 1
1 2 10
*/

Wa on test #7

玄关求调