SPOJ 1027

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();
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>