[POJ] 1724 ROADS

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<limits.h>
  4 #include<stdbool.h>
  5 int i,j,n,m,ki,r,x,y,z,p,tot,length,
  6     toit[110000],list[110],next[110000],cost[110000],
  7     q[500000],len[110000],dist[110][11000];
  8 
  9 bool can[110];
 10 int 
 11 pre()
 12 {
 13     memset(toit,0,sizeof(toit));
 14     memset(list,0,sizeof(list));
 15     memset(next,0,sizeof(next));
 16     memset(dist,3,sizeof(dist));
 17     memset(cost,0,sizeof(cost));
 18     memset(can,true,sizeof(can));
 19     memset(len,0,sizeof(len));
 20     tot=0;length=35111111;
 21     return 0;
 22 }
 23 
 24 int 
 25 min(int a,int b)
 26 {
 27     if(a<b) return(a);
 28     else return(b);
 29 }
 30 
 31 int 
 32 add(int x,int y,int z,int p)
 33 {
 34     tot++;
 35     toit[tot]=y;
 36     next[tot]=list[x];
 37     list[x]=tot;
 38     cost[tot]=p;
 39     len[tot]=z;
 40     
 41     return 0;
 42 }
 43 
 44 int 
 45 spfa(int s)
 46 {
 47     int i,j,head,tail,v,k;
 48     head=0;tail=1;
 49     q[1]=s; 
 50     can[s]=false;
 51     
 52     while(head!=tail)
 53     {
 54         head=head%500000+1;
 55         v=q[head];
 56         k=list[v];
 57         
 58         while(k!=0)
 59         {                   
 60             for(i=cost[k];i<=ki;i++)
 61             if(dist[v][i-cost[k]]+len[k]<dist[toit[k]][i])
 62             {
 63                 dist[toit[k]][i]=dist[v][i-cost[k]]+len[k];
 64                 if(can[toit[k]])
 65                 {
 66                     tail=tail%500000+1;
 67                     q[tail]=toit[k];
 68                     can[toit[k]]=false;
 69                 }
 70             }
 71             k=next[k];
 72         }
 73         can[v]=true;
 74     }
 75     return 0;
 76 }
 77 
 78 int 
 79 init()
 80 {
 81     scanf("%d\n%d\n%d\n",&ki,&n,&r);
 82     for(i=1;i<=r;i++)
 83     {
 84         scanf("%d%d%d%d",&x,&y,&z,&p);
 85         add(x,y,z,p);
 86     }
 87     return 0;
 88 }
 89 
 90 int 
 91 main()
 92 {
 93     pre();
 94     init();
 95     dist[1][0]=0;
 96     spfa(1);
 97     
 98     for(i=0;i<=ki;i++)
 99     length=min(length,dist[n][i]);
100     
101     if(length==35111111) printf("-1\n");else
102     printf("%d\n",length);
103     return 0;
104 }
105