首页 > 代码库 > 空中楼阁 ( House )最短路

空中楼阁 ( House )最短路

题目描述:

话说Z4阴差阳错地来到了神秘岛。不久,他们发现,这是一个由n个小岛和一个中心岛组成的群岛,群岛之间有m座桥。令他们感到惊讶的是,这些桥并不是固定不变的,经较长时间的观察,发现它们会随时间作周期性的变化(即桥的两端会不断更换)。 
立方很早就留意到远远的那个中心岛了。他发现岛的上空好像有一个很巨大的东西,但实在太远了,看不清楚。此时jakrinchose得意地从身上拿出一个超高倍数望远镜,好像很自豪的样子,因为他平时专门用来看美女的工具此时终于派得上用场了。
“那是一间小屋!架在一棵好大好大的树上!”
“Terrific!我们也许可以暂时在那安顿,好用来遮风避雨!”
于是他们便决定前往中心岛上的那间空中楼阁。Z4的懒惰是出了名的,他们当然希望越早到越好,那么,你能帮帮他们吗?
为方便计算,Z4把小岛按1..n编号,0表示中心岛。Z4一开始在编号为1的小岛上。在岛上行走的时间忽略不计,过桥的时间为1个单位。岛上的桥变化的周期为T,在nT+i(n=0,1,2,…;i=1,2,…,T)时刻岛上的桥为第i种状态,一开始的时刻为1。两个小岛间可能有多条桥相连。在任一时刻,Z4可以选择过桥,也可以原地不动。当然,如果无桥可过,Z4只能在原地等待。

输入格式:

输入文件house.in的第一行包括三个整数n(1<=n<=80),m(1<=m<=10000)和T(1<=T<=10),分别表示小岛的个数,岛上桥的数量和桥改变的周期T。
接下来分别描述第1..T种状态,每种状态有m行,每行有两个整数a, b(0<=a,b<=n),表示这种状态时小岛a和b有一条桥相连。两状态之间用一空行隔开。

输出格式:

输出文件house.out仅有一个整数,表示Z4最少得花多少时间到达中心岛。如果Z4无法到达中心岛,则输出“Poor Z4!”。

样例输入:

4 5 2
1 2
1 3
1 4
2 0
4 0

1 3
1 3
2 3
4 3
3 0

样例输出:

2

数据范围:

见题目

时间限制:

1000

空间限制:

65536
 
 
 
 

初看觉得很复杂,因为可以停在原地……

其实只需要在原图的基础上每个点每个时间都对自己连一条边,然后跑一边最短路即可

SPFA是最吼的!!

 

#include<cstdio>
#include<algorithm>
#define INF 1e9
using namespace std;
int a[300000],ne[300000],fi[10][100],la[10][100],q[300000][2],d[10][100],b[10][100],n,m,TT,x,y,tot,s,t;
void add(int t,int x,int y){
    a[++tot]=y;
    (!fi[t][x])?fi[t][x]=tot:ne[la[t][x]]=tot;la[t][x]=tot;
}
int spfa(){
    for(int i=0;i<TT;i++)for(int j=0;j<=n;j++)d[i][j]=INF;d[0][s]=0;
    int H=0,T=0;q[++T][0]=0;q[T][1]=s;b[0][s]=1;
    while(H<T){
        int x=q[++H][1],t=q[H][0];
        b[t][x]=0;
        for(int i=fi[t][x];i;i=ne[i])
        if(d[(t+1)%TT][a[i]]>d[t][x]+1){
            d[(t+1)%TT][a[i]]=d[t][x]+1;
            if(!b[(t+1)%TT][a[i]]){
                b[(t+1)%TT][a[i]]=1;
                q[++T][0]=(t+1)%TT;
                q[T][1]=a[i];
            }
        }
    }
    int ans=INF;
    for(int i=0;i<TT;i++)ans=min(ans,d[i][t]);
    if(ans==INF)return 0;else return ans;
}
int main(){
    scanf("%d%d%d",&n,&m,&TT);
    for(int i=0;i<TT;i++)
    for(int j=0;j<m;j++){
        scanf("%d%d",&x,&y);
        add(i,x,y);
        add(i,y,x);
    }
    for(int i=0;i<TT;i++)
    for(int j=0;j<=n;j++)
    add(i,j,j);
    s=1;t=0;
    int ans=spfa();
    if(ans)printf("%d",ans);else printf("Poor Z4!");
}

 

 

 

空中楼阁 ( House )最短路