学步园

UVA_590

    根据到达时间，我们可以把图看成有K层，然后用SPFA求到各个点的最短路即可。

#include<stdio.h>
#include<string.h>
#define INF 1000000000
int N, K, G[15][15][40], T[15][15], f[15][1010];
int q[11000], d[11000], inq[15][1010];
int init()
{
int i, j, k;
    scanf("%d%d", &N, &K);
if(!N && !K)
return 0;
for(i = 0; i < N; i ++)
for(j = 0; j < N; j ++)
        {
if(i == j)
continue;
            scanf("%d", &T[i][j]);
for(k = 0; k < T[i][j]; k ++)
                scanf("%d", &G[i][j][k]);
        }
return 1;
}
void solve()
{
int i, j, k, x, t, rear, front, M = 10100, min;
for(i = 0; i < N; i ++)
for(j = 1; j <= K; j ++)
            f[i][j] = INF;
    min = INF;
    front = rear = 0;
    memset(inq, 0, sizeof(inq));
    d[rear] = q[rear] = 0;
    rear ++;
while(front != rear)
    {
        x = q[front];
        t = d[front];
        inq[x][t] = 0;
if(t == K)
        {
if(x == N - 1 && f[x][t] < min)
                min = f[x][t];
        }
else
        {
for(i = 0; i < N; i ++)
if(i != x && T[x][i])
                {
                    k = t % T[x][i];
if(G[x][i][k] && f[x][t] + G[x][i][k] < f[i][t + 1])
                    {
                        f[i][t + 1] = f[x][t] + G[x][i][k];
if(!inq[i][t + 1])
                        {
                            q[rear] = i;
                            d[rear] = t + 1;
                            rear ++;
if(rear > M)
                                rear = 0;
                            inq[i][t + 1] = 1;
                        }
                    }
                }
        }
        front ++;
if(front > M)
            front = 0;
    }
if(min == INF)
        printf("No flight possible.\n");
else
        printf("The best flight costs %d.\n", min);
}
int main()
{
int t = 0;
while(init())
    {
        printf("Scenario #%d\n", ++ t);
        solve();
        printf("\n");
    }
return 0;
}