SP338 ROADS

题目描述

城市中有R条有向马路，n个马路连接点，通过每条马路都要花去一定费用。你现在在编号为1的连接点，手里有k元钱，要去n号连接点的最短路径的长度是多少？途中经过道路的花费不能超过k。注意：两个马路连接点间可能有多条马路

输入格式

第一行，k(0 <= K <= 10000)

第二行，n(2 <= N <= 100)

第三行，R(1 <= R <= 10000)

以下R行

x y L t 从x到y的马路，长度L(1<=每条马路的长度<=100)，花费t(0<=每条马路的费用<=100)

输出格式

满足条件最短路长度

很裸的二维最短路题。

不同于普通最短路的地方是，这里多了一维限制——花费不能超过k。在这个前提下，需要路径最短。

首先，题目并不要求花费最少。所以我们只需要不超过k即可。那么我们在松弛时，只需要判断花费不超过k即可。时间复杂度还是O((N+M)log(N+M))

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

#define maxn 101

#define maxm 10001

using namespace std;

struct edge{

    int to,dis,c,next;

    edge(){}

    edge(const int &_to,const int &_dis,const int &_c,const int &_next){ to=_to,dis=_dis,c=_c,next=_next; }

}e[maxm];

int head[maxn],k;

struct node{

    int now,dis,cost;

    node(){}

    node(const int &_now,const int &_dis,const int &_cost){ now=_now,dis=_dis,cost=_cost; }

    bool operator<(const node &x)const{ return dis>x.dis; }

};

priority_queue<node> q;

int n,m,w,ans;

inline int read(){

    register int x(0),f(1); register char c(getchar());

    while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }

    while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

    return x*f;

}

inline void dijkstra(){

    q.push(node(1,0,0));

    while(q.size()){

        int u=q.top().now,d=q.top().dis,c=q.top().cost; q.pop();

        if(u==n){ ans=d; return; }

        for(register int i=head[u];~i;i=e[i].next){

            int v=e[i].to;

            if(c+e[i].c<=w) q.push(node(v,d+e[i].dis,c+e[i].c));

        }

    }

}

int main(){

    int t=read();

    while(t--){

        memset(head,-1,sizeof head),k=0,ans=-1;

        while(q.size()) q.pop();

        w=read(),n=read(),m=read();

        for(register int i=1;i<=m;i++){

            int u=read(),v=read(),w=read(),c=read();

            e[k]=edge(v,w,c,head[u]),head[u]=k++;

        }

        dijkstra();

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

SP338 ROADS

题目描述

输入格式

第一行，k(0 <= K <= 10000)

第二行，n(2 <= N <= 100)

第三行，R(1 <= R <= 10000)

以下R行

x y L t 从x到y的马路，长度L(1<=每条马路的长度<=100)，花费t(0<=每条马路的费用<=100)

输出格式

满足条件最短路长度

很裸的二维最短路题。

不同于普通最短路的地方是，这里多了一维限制——花费不能超过k。在这个前提下，需要路径最短。

首先，题目并不要求花费最少。所以我们只需要不超过k即可。那么我们在松弛时，只需要判断花费不超过k即可。时间复杂度还是O((N+M)log(N+M))

最新文章

热门文章