Source Code

Problem: 1724  User: yzhw 
Memory: 1248K  Time: 32MS 
Language: G++  Result: Accepted 

Source Code 
# include <cstdio>
# include <queue>
# include <vector>
# include <cstring>
using namespace std;
struct node
{
   int t,len,money,next;
}l1[10001],l2[10001];
struct knode
{
   int t,len,money;
};
int g1[101],g2[101];
int count1=0,count2=0;
int dis[101];
int n,m,k;
struct cmp
{
  bool operator()(int a,int b)
  {
     return dis[a]>dis[b];
  }
};
struct cmp1
{
   bool operator()(knode a,knode b)
   {
      return a.len+dis[a.t]>b.len+dis[b.t];
   }
};
void insert(node l[],int v1,int v2,int g[],int &c,int len,int money)
{
   l[c].t=v2;
   l[c].money=money;
   l[c].next=g[v1];
   l[c].len=len;
   g[v1]=c++;
}
int main()
{
    scanf("%d %d %d",&k,&n,&m);
    for(int i=1;i<=n;i++)
       g1[i]=g2[i]=-1;
    for(int i=1;i<=m;i++)
    {
      int v1,v2,len,money;
      scanf("%d%d%d%d",&v1,&v2,&len,&money);
      insert(l1,v1,v2,g1,count1,len,money);
      insert(l2,v2,v1,g2,count2,len,money);      
    }
    {
      priority_queue<int,vector<int>,cmp> q;
      dis[n]=0;
      q.push(n);
      bool used[101];
      memset(used,0,sizeof(used));
      while(!q.empty())
      {
        int top=q.top();
        q.pop();
        if(used[top]) continue;
        used[top]=true;
        for(int p=g2[top];p!=-1;p=l2[p].next)
        {
           if(dis[l2[p].t]>dis[top]+l2[p].len)
             {
                dis[l2[p].t]=dis[top]+l2[p].len;
                q.push(l2[p].t);
             }
        }
      }
    }
    {
        priority_queue<knode,vector<knode>,cmp1> q;
        knode pos,tmp;
        pos.len=0;
        pos.t=1;
        pos.money=0;
        q.push(pos);
        while(!q.empty())
        {
          pos=q.top();
          q.pop();
          if(pos.t==n)
          {
            printf("%d\n",pos.len);
            goto end;
          }
          for(int p=g1[pos.t];p!=-1;p=l1[p].next)
          {
             tmp.t=l1[p].t;
             tmp.money=pos.money+l1[p].money;
             tmp.len=pos.len+l1[p].len;
             if(tmp.money<=k)
               q.push(tmp);
          }
        }
    }
    printf("-1\n");
    end:;
  //  system("pause");
    return 0;
}