题意
每条路有一个长度和一个花费，在花费限制内求从1 到n的最短路。
分析
只要能走到（有道路相连并且花费小于限制）就加入队列，队列中以距离为第一关键字，花费为第二关键字排序。
代码
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define maxn 10100
#define INF 1000000000-1
using namespace std;
struct edge{
int to,val,cost;
edge(
int to,
int val,
int cost){
this->to=to;
this->val=val;
this->cost=cost;
}
};
struct state{
int num,val,cost;
};
bool operator < (
const state &a,
const state &b){
if(a.val==b.val)
return a.cost>b.cost;
else return a.val>b.val;
}
typedef struct state state;
typedef struct edge edge;
int w,n,k,s,D,l,t;
int d[maxn];
vector<edge> g[maxn];
void Dij(){
priority_queue<state> q;
memset(d,
0x3f,
sizeof(d));
int ans=INF;
state ini;
ini.num=
1; ini.val=
0; ini.cost=
0;
q.push(ini);
while(!q.empty()){
state cur=q.top(); q.pop();
int curn=cur.num,curv=cur.val,curc=cur.cost;
if(curn==n){
ans=curv;
break;
}
for(
int i=
0;i<g[curn].size();i++){
int temp=g[curn][i].to;
if(curc+g[curn][i].cost<=w){
state p;
p.num=temp; p.val=curv+g[curn][i].val; p.cost=curc+g[curn][i].cost;
q.push(p);
}
}
}
if(ans<INF)
printf(
"%d",ans);
else printf(
"-1");
return;
}
int main(){
freopen(
"roads.in",
"r",stdin);
freopen(
"roads.out",
"w",stdout);
scanf(
"%d",&w);
scanf(
"%d",&n);
scanf(
"%d",&k);
for(
int i=
1;i<=k;i++){
scanf(
"%d%d%d%d",&s,&D,&l,&t);
g[s].push_back(edge(D,l,t));
}
Dij();
return 0;
}
转载于:https://www.cnblogs.com/leotan0321/p/6081399.html
相关资源：电商面试常问的一个算法实现，即最短路径和最省路费的问题
