UVA-10801 Lift Hopping (最短路)

题目大意及分析:一道简单的最短路。。。好几天没写程序了,憋得难受!!!

代码如下:

# include<iostream>
# include<cstdio>
# include<cstring>
# include<vector>
# include<queue>
# include<algorithm>
using namespace std; const int INF=1<<30; struct Edge
{
int to,w,nxt;
};
Edge G[35000];
int a[5][105],n,t;
int v[5],head[505],cnt;
int d[505]; bool read(int &val)
{
val=0;
char c;
while(c=getchar()){
if(c=='\n') return false;
else if(c==' ') return true;
else val=val*10+c-'0';
}
} void addEdge(int fr,int to,int w)
{
G[cnt].to=to;
G[cnt].w=w;
G[cnt].nxt=head[fr];
head[fr]=cnt++; G[cnt].to=fr;
G[cnt].w=w;
G[cnt].nxt=head[to];
head[to]=cnt++;
} int spfa()
{
fill(d,d+500,INF);
queue<int>q;
for(int i=0;i<500;i+=100){
d[i]=0;
q.push(i);
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=G[i].nxt){
int nu=G[i].to;
if(d[nu]>d[u]+G[i].w){
d[nu]=d[u]+G[i].w;
q.push(nu);
}
}
}
int res=INF;
for(int i=0;i<500;i+=100)
res=min(res,d[t+i]);
return res;
} int main()
{
while(~scanf("%d%d",&n,&t))
{
for(int i=0;i<n;++i) scanf("%d",v+i);
cnt=0;
memset(head,-1,sizeof(head));
getchar();
for(int i=0;i<n;++i){
a[i][0]=0;
int val;
while(read(val))
{
a[i][++a[i][0]]=val;
}
a[i][++a[i][0]]=val;
}
for(int i=0;i<n;++i)
for(int j=1;j<=a[i][0];++j)
for(int k=j+1;k<=a[i][0];++k)
addEdge(i*100+a[i][j],i*100+a[i][k],(a[i][k]-a[i][j])*v[i]);
for(int i=0;i<100;++i)
for(int j=0;j<500;j+=100)
for(int k=j+100;k<500;k+=100)
addEdge(i+j,i+k,60);
int ans=spfa();
if(ans==INF)
printf("IMPOSSIBLE\n");
else printf("%d\n",ans);
}
return 0;
}

  

上一篇:剑指offer计划20( 搜索与回溯算法中等)---java


下一篇:SQL group by底层原理——本质是排序,可以利用索引事先排好序