这题的实质上是最短路径问题。
大意：从1到N的路程总花费小于等于K的最短路径。
每条路有花费和长度。
依旧采用迪杰斯特拉的贪心思路，每次贪最短的，根据这个点来更新其他的点。
这题我没有注意的是加限制的优先队列的性质：
优先队列的元素保证都是到目标点的花费小于等于K的，这样下来，以长度为第一维度排序的优先队列，第一次到达目标点为终点的时候，此时的len即为所求。
我在这个点坑爹的TLE了。另外由于没有消掉文件读写WA了两次。
#include<iostream>
#include<queue>
#define INF 0x3FFFFFFF
using namespace std;struct ROADS
{int v,len,roll;int next;ROADS(){next=-1;}
}road[22222];int ptr[111];struct NODE
{
//public:int v,len,roll;friend bool operator <( NODE a,NODE b ){return a.len>b.len;}NODE( int a=0,int b=0,int c=0 ){v=a;len=b;roll=c;}
};
int Ecnt;void addEdge( int u,int v,int len,int roll )
{road[Ecnt].v=v;road[Ecnt].len=len;road[Ecnt].roll=roll;road[Ecnt].next=ptr[u];ptr[u]=Ecnt++;
}int main()
{//freopen( "test.in","r",stdin );//freopen( "ans.out","w",stdout );int K,N,R;while( scanf("%d %d %d",&K,&N,&R )!=EOF ){memset( ptr,-1,sizeof(ptr) );Ecnt=0;int u,v,len,roll;for( int i=0;i<R;i++ ){scanf( "%d %d %d %d",&u,&v,&len,&roll );addEdge( u,v,len,roll );//addEdge( v,u,len,roll );}priority_queue<NODE> PQ;NODE temp(1,0,0);PQ.push(temp);int ans=-1;while( !PQ.empty() )//按dijstra每次取出最短的 {NODE cur=PQ.top();PQ.pop();if( cur.v==N ){ans=cur.len;break;}for( int i=ptr[cur.v];i!=-1;i=road[i].next ){if( cur.roll+road[i].roll<=K ){temp.v=road[i].v;temp.len=cur.len+road[i].len;temp.roll=cur.roll+road[i].roll;PQ.push(temp);}}}printf( "%d\n",ans );}return 0;
}