POJ 1724 ROADS

点击打开链接

ROADS

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 10202   Accepted: 3786

Description

N cities named with numbers 1 ... N are connected with one-way roads. Each road has two parameters associated with it : the road length and the toll that needs to be paid for the road (expressed in the number of coins).

Bob and Alice used to live in the city 1. After noticing that Alice was cheating in the card game they liked to play, Bob broke up with her and decided to move away - to the city N. He wants to get there as quickly as possible, but he is short on cash.

We want to help Bob to find the shortest path from the city 1 to the city N that he can afford with the amount of money he has.

Input

The first line of the input contains the integer K, 0 <= K <= 10000, maximum number of coins that Bob can spend on his way.

The second line contains the integer N, 2 <= N <= 100, the total number of cities.

The third line contains the integer R, 1 <= R <= 10000, the total number of roads.

Each of the following R lines describes one road by specifying integers S, D, L and T separated by single blank characters :

  • S is the source city, 1 <= S <= N
  • D is the destination city, 1 <= D <= N
  • L is the road length, 1 <= L <= 100
  • T is the toll (expressed in the number of coins), 0 <= T <=100

Notice that different roads may have the same source and destination cities.

Output

The first and the only line of the output should contain the total length of the shortest path from the city 1 to the city N whose total toll is less than or equal K coins.

If such path does not exist, only number -1 should be written to the output.

Sample Input

5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2

Sample Output

11

有n个城市,m条路,初始时你有k个金币,每条路都有一个长度以及经过这条路的花费,问在你能够承受的花费之内,从1号城市到n号城市之间的最短距离是多少。

可以用dfs进行递归回溯也可以用bfs优先队列,事实表明,优先队列的效率比较高。

dfs就是从1号开始进行逐层递归遍历所有情况,一旦金币数量不能满足花费,就退出递归,直到找到最短的路径。

优先队列是按照路径从小到大排序,那么没找到一个符合条件的点就加入到队列中,直至找到n号点。

//332K	94MS
#include<stdio.h>
#include<string.h>
#define M 107
#define inf 0x3f3f3f
int head[M],vis[M],nodes,minlen;
int n,m,k;
struct E
{
    int u,v,l,c,next;
} edge[M*M];
void addedge(int u,int v,int l,int c)
{
    edge[nodes].u=u;
    edge[nodes].v=v;
    edge[nodes].l=l;
    edge[nodes].c=c;
    edge[nodes].next=head[u];
    head[u]=nodes++;
}
void dfs(int city,int nowlen,int nowmoney)
{
    if(nowlen>minlen)return;
    if(city==n&&nowlen<minlen&&nowmoney>=0)
    {
        minlen=nowlen;
        return;
    }
    for(int i=head[city]; i!=-1; i=edge[i].next)
    {
        int v=edge[i].v;
        int l=edge[i].l;
        int c=edge[i].c;
        if(!vis[v]&&nowmoney>=c)
        {
            vis[v]=1;
            dfs(v,nowlen+l,nowmoney-c);
            vis[v]=0;
        }
    }
    return;
}
int main()
{
    memset(head,-1,sizeof(head));
    memset(vis,0,sizeof(vis));
    nodes=0,minlen=inf;
    scanf("%d%d%d",&k,&n,&m);
    int u,v,l,c;
    while(m--)
    {
        scanf("%d%d%d%d",&u,&v,&l,&c);
        addedge(u,v,l,c);
    }
    dfs(1,0,k);
    if(minlen==inf)printf("-1\n");
    else
        printf("%d\n",minlen);
}
//1028K	32MS
#include<stdio.h>
#include<string.h>
#include<queue>
#define M 1007
using namespace std;
int head[M],nodes;
int k,n,m;
struct Q
{
    int pos,len,money;
    bool operator<(const Q t)const
    {
        return t.len<len;
    }
} ;
struct node
{
    int u,v,next,l,c;
}edge[M*M];
void addedge(int u,int v,int l,int c)
{
    edge[nodes].u=u;
    edge[nodes].v=v;
    edge[nodes].l=l;
    edge[nodes].c=c;
    edge[nodes].next=head[u];
    head[u]=nodes++;
}
int bfs(int u)
{
    priority_queue<Q>q;
    Q now,next;
    now.pos=1;
    now.len=0;
    now.money=0;
    q.push(now);
    while(!q.empty())
    {
        now=q.top();
        q.pop();
        int pos=now.pos,len=now.len,money=now.money;
        if(pos==n&&money<=k)return len;
        for(int i=head[pos];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            int l=edge[i].l;
            int c=edge[i].c;
            if(money+c<=k)
            {
                next.pos=v;
                next.len=len+l;
                next.money=money+c;
                q.push(next);
            }
        }
    }
    return -1;
}
int main()
{
    scanf("%d%d%d",&k,&n,&m);
    nodes=0;
    memset(head,-1,sizeof(head));
    int u,v,l,c;
    for(int i=0; i<m; i++)
    {
        scanf("%d%d%d%d",&u,&v,&l,&c);
        addedge(u,v,l,c);
    }
    int ans=bfs(1);
    printf("%d\n",ans);
}

POJ 1724 ROADS,布布扣,bubuko.com

时间: 05-06

POJ 1724 ROADS的相关文章

深搜+剪枝 POJ 1724 ROADS

POJ 1724 ROADS Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 12766   Accepted: 4722 Description N cities named with numbers 1 ... N are connected with one-way roads. Each road has two parameters associated with it : the road length and

poj 1724 ROADS (bfs+优先队列)

题目链接 题意:在有费用k限制的条件下,求从1到n的最短距离,如果最短距离相同求费用最小的,边为有向边,其中可能有 多个相同的源点和目标点,但是距离和费用不同. 分析:用bfs和邻接表来把每一个边搜一下,因为用了优先队列,所以先到n的一定是最小的 . 1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cstdio&

poj 1251--Jungle Roads(求最小生成树)

Jungle Roads Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 20154   Accepted: 9291 Description The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some

POJ 1724 二维费用最短路

题目大意:有N个城市,编号1-N有R条路,每条路(单向)的起点为Si,终点为Di,长度为Li,如果要走这条路需要花Ti的钱现在你只有K元钱,求在不超支的前提下,从1走到N需要的最短距离 这里总是希望路程尽可能的短,那么利用dijkstra的方法来解决问题,总是先扩展距离近的点,这样能更快的找到终点的最短路 节点的扩展满足二维的情况,只要路程和费用两个限制条件中的其中一个满足情况那么当前节点便要扩展 用cost[i],dis[i]记录在i节点所能达到的最优状态,只有某个情况left>cost[v]

POJ 3411-Paid Roads(状态压缩+dijkstra算法+floyd-warshall算法)

题目大意:给出一张有向图,求点1到点N的最短路,不同的是,对于每一条边,除了源点目标点和花费以外,还有额外点c,若走这条边之前到达过c点,花费会减少到另一个值P.如果最短路不存在,输出impossible. 先用floyd-warshall算法判断连通性,此时忽略额外的c和P. 然后用dijkstra算法,用d[i][S]表示在点i且经过了S集合的点的最短路,将每一个d[i][S]都看成一个点,用dijkstra算法计算. #include<stdio.h> #include<stdli

poj 最短路径题目总会

求最短路基本的算法:1>Dijkstra算法2>Bellman-Ford算法3>Floyd算法4>Floyd-Warshall算法5>Johnson算法6>A*算法题目: 1.poj1062 昂贵的聘礼(中等) 此题是个经典题目:用Dijkstra即可:但是其中的等级处理需要一定的技巧: 要理解好那个等级制度:这个处理好,基本就是裸体Dijkstra: 2 poj1125 Stockbroker Grapevine(基本) 这个是简单Floyd,需要求出的是每对顶点之间

图论 500题——主要为hdu/poj/zoj

转自——http://blog.csdn.net/qwe20060514/article/details/8112550 =============================以下是最小生成树+并查集======================================[HDU]1213   How Many Tables   基础并查集★1272   小希的迷宫   基础并查集★1325&&poj1308  Is It A Tree?   基础并查集★1856   More i

POJ题目分类推荐 (很好很有层次感)

著名题单,最初来源不详.直接来源:http://blog.csdn.net/a1dark/article/details/11714009 OJ上的一些水题(可用来练手和增加自信) (POJ 3299,POJ 2159,POJ 2739,POJ 1083,POJ 2262,POJ 1503,POJ 3006,POJ 2255,POJ 3094) 初期: 一.基本算法: 枚举. (POJ 1753,POJ 2965) 贪心(POJ 1328,POJ 2109,POJ 2586) 递归和分治法. 递

题单二:图论500

http://wenku.baidu.com/link?url=gETLFsWcgddEDRZ334EJOS7qCTab94qw5cor8Es0LINVaGMSgc9nIV-utRIDh--2UwRLvsvJ5tXFjbdpzbjygEdpGehim1i5BfzYgYWxJmu ==========  以下是最小生成树+并查集=========================[HDU]1213         How Many Tables        基础并查集★1272         小