[luogu] P1841 [JSOI2007]重要的城市 Floyd性质

前言

卡输出卡死了QAQ 传送门 :

思路

题目要求的是, a 到 b a 到 b a到b 有且只有一条路上面的点的数量

所以我们可以在更新的时候直接用一个 a n s [ i ] [ j ] ans[i][j] ans[i][j]存一下答案

但是如果存在 [ i , j ] = = [ i , k , j ] [i,j] ==[i,k,j] [i,j]==[i,k,j] 那么就说明多条最短路

因此我们需要特判这条最后记录答案输出即可

CODE

int n,m,t;
int dist[N][N];
int ans[N][N];
int b[N];

void cal()
{

}


void solve()
{
	cin>>n>>m;
	memset(dist,0x3f,sizeof dist);
	
	while(m -- )
	{
		int a,b,c;
		cin>>a>>b>>c;
		dist[a][b] = dist[b][a] = min(dist[a][b],c);
	}

	
	for(int k=1;k