題目鏈接: hdu 4396
題目大意: 給出帶權值的無向邊,可能會有自環
給出起點和終點,求至少經過K條邊的最短路徑
解題思路: 當k不能被10整除時,K=k%10+1,否則K=k%10;
二維SPFA,Dp[ a ][ b ]表示經過b條邊到達a點的最短路徑
剪枝的地方是把b>K的看成b=K,因為b>=K的都是滿足題意的答案
把b>K並入b=K,省去無用的搜素,降低時間復雜度
代碼:
#include#include #include #define MAX 5010 #define INF 0x3f3f3f3f int Dp[MAX][505],pre[MAX],Index,visit[MAX][505]; struct snode{ int to,w,next; }Edge[210000]; struct node{ int v,len; }listb[2000000],v1,v2; void Add_edge(int a,int b,int c) { Edge[Index].to=b; Edge[Index].w=c; Edge[Index].next=pre[a]; pre[a]=Index++; } int SPFA(int a,int b,int c) { int s,e,i,vv,vlen; memset(visit,0,sizeof(visit)); s=e=0; Dp[a][0]=0; v1.len=0,v1.v=a; listb[s++]=v1; while(s!=e) { v1=listb[e++]; visit[v1.v][v1.len]=0; for(i=pre[v1.v];i!=-1;i=Edge[i].next) { vlen=v1.len+1; if(vlen>=c) //把 len>K的看成K vlen=c; vv=Edge[i].to; if(Dp[vv][vlen]>Dp[v1.v][v1.len]+Edge[i].w) { Dp[vv][vlen]=Dp[v1.v][v1.len]+Edge[i].w; //更新 if(!visit[vv][vlen]) //防止重復人隊列 { v2.v=vv,v2.len=vlen; visit[vv][vlen]=1; listb[s++]=v2; } } } } return Dp[b][c]; } int main() { int i,j,n,m,a,b,c,t; while(scanf("%d%d",&n,&m)!=EOF) { Index=0; memset(pre,-1,sizeof(pre)); memset(Dp,INF,sizeof(Dp)); for(i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); Add_edge(a,b,c); Add_edge(b,a,c); } scanf("%d%d%d",&a,&b,&c); t=c; c/=10; if(t%10!=0) //至少為c分,既>=c c++; t=SPFA(a,b,c); if(t==INF) printf("-1\n"); else printf("%d\n",t); } return 0; }