Untitled

By Lunatch, ago, written in C++.
URL http://pastecode.org/index.php/view/74830662
Download Paste or View RawExpand paste to full width of browser | Change Viewing Options
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<algorithm>
  4. #include<queue>
  5. using namespace std;
  6. #define inf 0x3f3f3f3f
  7. const int maxn=10005;
  8. int num,first[maxn];
  9. struct node
  10. {
  11.     int id;
  12.     int len;
  13.     int val;
  14. }node1;
  15. struct edge
  16. {
  17.     int id;
  18.     int len;
  19.     int val;
  20.     int next;//作用跟next数组一样
  21. }e[maxn];
  22. priority_queue<node>q;
  23. bool operator <(node a,node b)
  24. {
  25.     return a.len>b.len;
  26. }
  27. void add(int u,int v,int len,int val)
  28. {
  29.     e[num].id=v;//存下一个点,以边找点
  30.     e[num].val=val;
  31.     e[num].len=len;
  32.     e[num].next=first[u];
  33.     first[u]=num;
  34.     num++;
  35. }
  36. int main()
  37. {
  38.     node cur;
  39.     int ans=inf;
  40.     int k,n,r,s,d,l,t;
  41.     scanf("%d%d%d",&k,&n,&r);
  42.     memset(first,-1,sizeof(first));
  43.     while(!q.empty()) q.pop();
  44.     num=0;
  45.     for(int i=0;i<r;i++)
  46.     {
  47.         scanf("%d%d%d%d",&s,&d,&l,&t);
  48.         add(s,d,l,t);
  49.     }
  50.     node1.id=1;//起始点
  51.     node1.len=0;
  52.     node1.val=0;
  53.     q.push(node1);
  54.     while(!q.empty())
  55.     {
  56.         cur=q.top();
  57.         q.pop();
  58.         if(cur.id==n)
  59.         {
  60.             ans=cur.len;
  61.             break;
  62.         }
  63.         for(int i=first[cur.id];i!=-1;i=e[i].next)
  64.         {
  65.             if(k>=cur.val+e[i].val)//只有符合要求的点才会进入队列
  66.             {
  67.                 node1.id=e[i].id;
  68.                 node1.len=e[i].len+cur.len;
  69.                 node1.val=e[i].val+cur.val;
  70.                 q.push(node1);
  71.             }
  72.         }
  73.     }
  74.     if(ans==inf)
  75.         printf("-1\n");
  76.     else
  77.     printf("%d\n",ans);
  78. }

Here you can reply to the paste above

Make Private

   

Feeling clever? Set some advanced options.