乘车路线

乘车路线( 二维spfa(star ))

时限：(1s) 内存：(256M)

Descrption

编号为 (1sim N) 的 (N) 座城镇用若干仅供单向行驶的道路相连，每条道路上均有两个参数：道路长度((length))和在该条道路上行驶的费用（(cost)）。
(BOB) 准备从城镇 (1) 出发到达城镇 (N)，但他目前只有 (W) 的钱，为此，你需要帮助他寻找一条从城镇 (1) 到城镇 (N) 在他能支付的前提下的一条最短路线。

Input

(W N M)（(N)为城镇数目，(2<=N<=100)，(M) 为道路条数，(1<=M<=10000,W) 为钱的数目，(0<=W<=1000)）
随后的 (M) 行每行为一条道路的信息，包含 (4) 个数值（(u,v,w,cost)），表示从城镇 (u) 到 (v) 有一条长度为 (w) 的单向道路，经过这条道路需要花费 (cost) 。((1<=u,v<=N,1<=w<=100,0<=cost<=100))

Output

输出最短长度，若无解，则输出“(NO)”；

Sample Input

Sample Output

Hint

来源：(Poj 1724)

分析

典型的二维 (spfa)。
限制条件有两个，距离是求最短，费用只要达标即可，所以加一维限制下费用。
定义：(dis[i][j]) 表示 (i) 到源点花费了 (j) 钱的最短距离。

Code

#include <bits/stdc++.h>
const int maxn=100+5,maxm=1e4+5,Inf=0x3f3f3f3f;
struct Node{
    int to,w,cost,next;
}e[maxm];
int dis[maxn][1005],vis[maxn][1005],head[maxn];
int n,m,W,len;
void Insert(int u,int v,int w,int c){
    e[++len].to=v;e[len].w=w;e[len].cost=c;e[len].next=head[u];head[u]=len;
}
void Spfa(int x){
    memset(dis,0x3f,sizeof(dis));
    std::queue< std::pair<int,int> > q;
    dis[x][0]=0;q.push(std::make_pair(x,0));
    while(!q.empty()){
        std::pair<int,int> t=q.front();q.pop();
        int u=t.first,money=t.second;
        vis[u][money]=0;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to,w=e[i].w,c=e[i].cost,y;
            if(money+c>W)continue;//超预算了
            if(dis[v][money+c]>(y=dis[u][money]+w)){
                dis[v][money+c]=y;
                if(!vis[v][money+c]){
                    vis[v][money+c]=1;
                    q.push(std::make_pair(v,money+c));
                }
            }
        }
    }
    int ans=Inf;
    for(int i=0;i<=W;++i)//从到达目标的的所有费用中找一个最短的
        ans=std::min(ans,dis[n][i]);
    if(ans==Inf)
        printf("NO
");
    else
        printf("%d
",ans);
}
void Solve(){
    scanf("%d%d%d",&W,&n,&m);
    for(int i=1;i<=m;++i){
        int u,v,w,c;scanf("%d%d%d%d",&u,&v,&w,&c);
        Insert(u,v,w,c);
    }
    Spfa(1);
}
int main(){
    Solve();
    return 0;
}