Light OJ 1174 - Commandos (Floyd)


転送ゲート:http://lightoj.com/volume_showproblem.php?problem=1174
突撃小隊は敵の本部のある場所から爆弾を放ち始め、敵の本部の各建物はすべて連通していて、爆弾は無限で、小隊の中の隊員は無限で、すべての隊員は起点から一緒に出発して、それぞれ自分の爆弾を置く経路を選ぶことができて、すべての場所は爆弾を放ちます.各選手が1つの場所から1つの場所に移動する時間は1つの時間単位で、あるゴールの最短時間を尋ねます.
解題構想:Floydによってdist[起点][ある場所i]とdist[ある場所i][終点]を求め,両者を加算する最大値が答えである.
証明:起点から終点までの道に、乗り継ぎの場所があり、まずこの場所に入ってから出なければならないので、dist[start][inner]+dist[innner][end]です.
Code:
/*   W          w           w        mm          mm             222222222       7777777777777    */
/*    W        w w         w        m  m        m  m          222        22              7777    */
/*    w        w w         w        m  m        m  m                     22              777     */
/*     w      w   w       w        m    m      m    m                    22              77      */
/*     w      w    w      w        m    m      m    m                 222                77      */
/*      w    w      w    w        m      m    m      m              222                  77      */
/*      w    w      w    w        m      m    m      m            222                    77      */
/*       w  w        w  w        m        m  m        m         222                      77      */
/*       w  w        w  w        m        m  m        m      222                         77      */
/*        ww          ww        m          mm          m     222222222222222             77      */

//#pragma comment(linker, "/STACK:102400000,102400000")
//C++
//int size = 256 << 20; // 256MB
//char *p = (char*)malloc(size) + size;
//__asm__("movl %0, %%esp
" :: "r"(p));
//G++ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define REP(i,s,t) for(int i=(s);i<=(t);i++) #define REP2(i,t,s) for(int i=(t);i>=s;i--) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef unsigned long ul; const int MAXN=105; int T; int n,R; int S,D; struct FUCK { int n; int d[MAXN][MAXN]; void init(int n) { this->n=n; memset(d,-1,sizeof(d)); REP(i,0,n-1) { d[i][i]=0; } } void addedge(int u,int v) { d[u][v]=d[v][u]=1; } void floyd() { REP(k,0,n-1) { REP(i,0,n-1) { REP(j,0,n-1) { if(d[i][k]!=-1&&d[k][j]!=-1) { if(d[i][j]==-1) { d[i][j]=d[i][k]+d[k][j]; } else { d[i][j]=min(d[i][k]+d[k][j],d[i][j]); } } } } } } int solve() { int res=0; floyd(); REP(i,0,n-1) { if(d[S][i]!=-1&&d[i][D]!=-1) { res=max(res,d[S][i]+d[i][D]); } } return res; } void debug() { REP(i,0,n-1) { REP(j,0,n-1) { printf("d[%d][%d]=%d
"
,i,j,d[i][j]); } } } }solver; int main() { #ifdef ONLINE_JUDGE #else freopen("test.in","r",stdin); #endif int ca=1; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&R); solver.init(n); REP(i,1,R) { int u,v; scanf("%d%d",&u,&v); solver.addedge(u,v); } scanf("%d%d",&S,&D); int ans=solver.solve(); printf("Case %d: %d
"
,ca++,ans); //solver.debug(); } return 0; }