ZOJ 2760最短パス本数問題

以前は最短パスの本数の問題をしたことがありますが、この問題はちょっと奇抜で、最短パス数ではパスを繰り返すことができません==....
繰り返し使えるのは簡単なのでdijで押せばいいです.始点を1に割り当て、隣接するエッジに自分を押します.0->1の2つのエッジが同じように短い場合、0->1は2回押すので、0->1には2つの歩き方があります.
この問題は違います.パスは繰り返してはいけません.so...私たちはそう考えることができます.
最パスで使用されるエッジを見つけ、エッジの容量を1に割り当てます.これにより、フローが通過し、始点から終点までのフローが通過すると、最短パスとして保証され、重複エッジがありません.
現在のテーマは、最短パスでエッジを探すことに変わります.
このようなエッジには、Path(s,i)+E(i,j)+Path(j,t)=Path(s,t):このようなエッジE(i,j)が最短経路にある;
このようなエッジを通過する最大ストリームは、最短パスのストライプ数です.
この問題は-1に達しないことに注意して、このINFの値はかなり大きくて、この原因のため...WAは長い間...

#include<iostream>
#include<cstdio>
#include<cstring>
#define MN 111
#define INF 0x0FFFFFFF
#define CC(a) memset(a,0,sizeof(a))
#define FF(i,a) for( int i=0;i<a;i++ )
template<class T> void inline checkmin( T &a,T b ){ if( a==-1||a>b )a=b; }
using namespace std;

int maze[MN][MN],map[MN][MN],N,s,t;
int cap[MN][MN];

void floyd()
{
 	 FF(i,N)FF(j,N)maze[i][j]=map[i][j];
 	 FF(i,N)maze[i][i]=0;
 	 for( int k=0;k<N;k++ )
 	 for( int i=0;i<N;i++ )
 	 for( int j=0;j<N;j++ )
 	 if( maze[i][k]!=-1&&maze[k][j]!=-1 )
 	 	 if( maze[i][j]==-1 )maze[i][j]=maze[i][k]+maze[k][j];
 	 	 else maze[i][j]=min( maze[i][j],maze[i][k]+maze[k][j] );
}

void setG()
{
 	 CC(cap);
 	 for( int i=0;i<N;i++ )
 	 for( int j=0;j<N;j++ )
 	 	  if( map[i][j]!=-1&&maze[s][i]!=-1&&maze[j][t]!=-1 )
 	 	  if( maze[s][i]+map[i][j]+maze[j][t]==maze[s][t] )
 	 	  	  cap[i][j]++;
}

int vis[MN],pre[MN],que[MN],a[MN];
bool bfs()
{
 	 CC(vis);
 	 int head=0,foot=0;
 	 que[foot++]=s;vis[s]=true;a[s]=INF;
 	 while( head<foot )
 	 {
	  		int u=que[head++];
	  		FF(v,N)
	  		if( !vis[v]&&cap[u][v] )
	  		{
			 	vis[v]=true;
			 	pre[v]=u;
			 	que[foot++]=v;
			 	a[v]=min( a[u],cap[u][v] );
			 	if( v==t )return true;
		   	}
	 }
	 return false;
}

int EK()
{
 	int maxflow=0;
 	while(bfs())
 	{
		maxflow+=a[t];
		int m=t;
		while( m!=s )
		{
		 	   cap[pre[m]][m]-=a[t];
		 	   cap[m][pre[m]]+=a[t];
		 	   m=pre[m];
  		}
	}
	return maxflow;
}

int main()
{
 	int i,j,c;
 	while( scanf("%d",&N)!=EOF )
	{
	 	   for( i=0;i<N;i++ )
	 	   for( j=0;j<N;j++ )
	 	   {
	 	   		scanf("%d",&map[i][j]);
	 	   		if( i==j ) map[i][j]=0;
		   }
		   scanf("%d%d",&s,&t);
		   if( s==t ){
		   	   printf("inf
");
		   	   continue;
		   }
		   floyd();
		   setG();
		   printf( "%d
",EK() );
 	}
 	return 0;
}