https://www.spoj.pl/problems/FPOLICE/

分层图最短路。。spfa。。。
怎么可能这么快0.02s？怀疑数据太水了。。。

#include<iostream>
#include<queue>
#include<vector>
#include<stdio.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=100,maxt=250+10,inf=~0U>>1;
int Time[maxn][maxn],Risk[maxn][maxn];
int dist[maxn][maxt];
bool inQ[maxn][maxt];
int N,T;
struct node
{
    int n,t;
    node(int n,int t):n(n),t(t) {}
};
queue<node> Q;
void solve()
{
    cin>>N>>T;
    REP(i,N) REP(j,N) scanf("%d",&Time[i][j]);
    REP(i,N) REP(j,N) scanf("%d",&Risk[i][j]);
    REP(i,N) REP(j,T+1) dist[i][j]=inf,inQ[i][j]=false;
    dist[0][0]=0;
    Q.push(node(0,0));
    inQ[0][0]=true;
    while(Q.size())
    {
        node cur=Q.front();
        Q.pop();
        inQ[cur.n][cur.t]=false;
        int cost=dist[cur.n][cur.t],get,nt;
        for(int i=0; i<N; i++) if(i!=cur.n)
            {
                if((nt=Time[cur.n][i]+cur.t)>T) continue;
                get=cost+Risk[cur.n][i];
                if(get<dist[i][nt])
                {
                    dist[i][nt]=get;
                    if(!inQ[i][nt])
                    {
                        Q.push(node(i,nt));
                        inQ[i][nt]=true;
                    }
                }
            }
    }
    int Min=inf,x=-1;
    REP(i,T+1)
    if(dist[N-1][i]<Min)
        Min=dist[N-1][i],x=i;
    if(x==-1)
    {
        cout<<-1<<endl;
        return;
    }
    cout<<Min<<" "<<x<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t–) solve();
}