題意:要從1到N的最短路并且每一條路上有對應(yīng)的花費要求,總花費不能大于給定的一個值K,輸出最短路徑的長度.
方法: 不僅要最短,還有花費限制,所以就想到用優(yōu)先隊列,來維護一個優(yōu)先級關(guān)系,使得答案最優(yōu).
AC代碼:
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<functional>
#include<vector>
#include<stack>
#include<map>
#include<cstdlib>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define PI acos(-1.0)
#define db double
#define mod 1000000007
using namespace std;
const int maxn = 1e4+5;
const int inf=1e9;
int k,n,r;
int cnt;
struct node
{
int to,w,c,next;
}s[maxn]; //模擬鏈表.
struct cmp //優(yōu)先隊列需要用.
{
int id,dis,cost;
bool operator < (const cmp &a) const { //以取&號的為準!
if(a.dis == dis ) return a.cost < cost ; //其次是花費小的優(yōu)先.
return a.dis < dis ; //先讓路最短的優(yōu)先.
}
};
int head[maxn];
void add(int u,int v, int w,int c) //模擬過程.
{
s[cnt].to=v,s[cnt].w=w,s[cnt].c=c;
s[cnt].next=head[u];
head[u]=cnt++;
}
void dij() //dij + 優(yōu)先隊列優(yōu)化!!! , 學會啊 !!!
{
priority_queue<cmp>q;
cmp a,b;
int res=inf;
a.id=1; //初始化情況
a.dis=0;
a.cost=0;
q.push(a);
while(!q.empty()){
b=q.top();
q.pop();
if(b.id == n){
res=b.dis; //已找到目標點,所以推出bfs.
break;
}
for(int i=head[b.id];i!=-1;i=s[i].next){
int to=s[i].to;
int w=s[i].w;
if(s[i].c + b.cost <= k){ //花費小于k.
a.id = to;
a.dis = b.dis + w;
a.cost = b.cost + s[i].c ;
q.push(a);
}
}
}
if(res == inf ) printf("-1\n");
else printf("%d\n",res);
}
int main()
{
scanf("%d %d %d",&k,&n,&r);
cnt=0;
memset(head,-1,sizeof(head));
for(int i=0;i<r;i++){
int u,v,w,c;
scanf("%d %d %d %d",&u,&v,&w,&c);
add(u,v,w,c); //單向邊,所以只需要加一次.
}
dij();
}
