• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            poj1860

            Currency Exchange

            Time Limit: 1000MS Memory Limit: 30000K
            Total Submissions: 11448 Accepted: 3857

            Description

            Several currency exchange points are working in our city. Let us suppose that each point specializes in two particular currencies and performs exchange operations only with these currencies. There can be several points specializing in the same pair of currencies. Each point has its own exchange rates, exchange rate of A to B is the quantity of B you get for 1A. Also each exchange point has some commission, the sum you have to pay for your exchange operation. Commission is always collected in source currency.
            For example, if you want to exchange 100 US Dollars into Russian Rubles at the exchange point, where the exchange rate is 29.75, and the commission is 0.39 you will get (100 - 0.39) * 29.75 = 2963.3975RUR.
            You surely know that there are N different currencies you can deal with in our city. Let us assign unique integer number from 1 to N to each currency. Then each exchange point can be described with 6 numbers: integer A and B - numbers of currencies it exchanges, and real RAB, CAB, RBA and CBA - exchange rates and commissions when exchanging A to B and B to A respectively.
            Nick has some money in currency S and wonders if he can somehow, after some exchange operations, increase his capital. Of course, he wants to have his money in currency S in the end. Help him to answer this difficult question. Nick must always have non-negative sum of money while making his operations.

            Input

            The first line of the input contains four numbers: N - the number of currencies, M - the number of exchange points, S - the number of currency Nick has and V - the quantity of currency units he has. The following M lines contain 6 numbers each - the description of the corresponding exchange point - in specified above order. Numbers are separated by one or more spaces. 1<=S<=N<=100, 1<=M<=100, V is real number, 0<=V<=103.
            For each point exchange rates and commissions are real, given with at most two digits after the decimal point, 10-2<=rate<=102, 0<=commission<=102.
            Let us call some sequence of the exchange operations simple if no exchange point is used more than once in this sequence. You may assume that ratio of the numeric values of the sums at the end and at the beginning of any simple sequence of the exchange operations will be less than 104.

            Output

            If Nick can increase his wealth, output YES, in other case output NO to the output file.

            Sample Input

            3 2 1 20.0
            1 2 1.00 1.00 1.00 1.00
            2 3 1.10 1.00 1.10 1.00
            

            Sample Output

            YES
            以貨幣為節點,邊上有兩個值,一個是rate,另一個是commission 顯然為有向邊 例如<i,j> 表示i to j 的 rate ,commission
            題目中最后一段木看明白啥意思
            寫錯了一個字母,改過后才A的
            還有就是代碼中采用了鏈式前向星,
            前向星是優化spfa的方法之一,可以用數組模擬鏈表來表示前向星
            需要一個索引,至索引頭節點,類似于鄰接表
            /*
             鏈式前向星
             int e,d,next[MAXM];
             int link[MAXN];
             link數組為索引數組,link[i]索引的是i這個節點,可以找到以i為頭結點的所有邊
             e數組建立尾節點表,d數組建立邊權表
             next數組把所有以i為頭結點的邊連接起來
             用link[i]志向兄弟中的一個,用next數組找到所有的兄弟,用e,d數組讀出尾節點和邊權
            */
             1#include<stdio.h>
             2#include<string.h>
             3#include<math.h>
             4#define MAX 10000
             5int n,num,now;
             6double total;
             7int s;
             8int e[MAX+5],next[MAX+5],link[MAX+5];
             9double rate[MAX+5],com[MAX+5];
            10short vis[MAX+5];
            11double dis[MAX+5];
            12int queue[MAX*5],head,tail;
            13void add(int a,int b,double k1,double k2)
            14{
            15    s++;
            16    e[s]=b;
            17    rate[s]=k1;
            18    com[s]=k2;
            19    next[s]=link[a];
            20    link[a]=s;
            21}

            22void init()
            23{
            24    int i,a,b;
            25    double rab,cab,rba,cba;
            26    scanf("%d %d %d %lf",&n,&num,&now,&total);
            27    s=0;
            28    memset(next,0,sizeof(next));
            29    memset(link,0,sizeof(link));
            30    for (i=1; i<=num ; i++ )
            31    {
            32        scanf("%d %d %lf %lf %lf %lf",&a,&b,&rab,&cab,&rba,&cba);
            33        add(a,b,rab,cab);
            34        add(b,a,rba,cba);
            35    }

            36}

            37short spfa()
            38{
            39    int i,u,j;
            40    memset(vis,0,sizeof(vis));
            41    queue[1]=now;
            42    for (i=0;i<=n ;i++ )
            43    {
            44        dis[0]=0;
            45    }

            46    dis[now]=total;
            47    vis[now]=1;
            48    head=0;
            49    tail=1;
            50    while (head<tail)
            51    {
            52        head++;
            53        u=queue[head];
            54        j=link[u];
            55        while (j!=0)
            56        {
            57            if ((dis[u]-com[j])*rate[j]>dis[e[j]])
            58            {
            59                dis[e[j]]=(dis[u]-com[j])*rate[j];
            60                if (!vis[e[j]])
            61                {
            62                    vis[e[j]]=1;
            63                    tail++;
            64                    queue[tail]=e[j];
            65                }

            66            }

            67            if (dis[now]>total)
            68            {
            69                return 1;
            70            }

            71            j=next[j];
            72        }

            73        vis[u]=0;
            74    }

            75    return 0;
            76}

            77int main()
            78{
            79    init();
            80    if (spfa()==1)
            81        printf("YES\n");
            82    else printf("NO\n");
            83    return 0;
            84}

            85

            posted on 2012-02-12 11:56 jh818012 閱讀(387) 評論(0)  編輯 收藏 引用

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            常用鏈接

            留言簿

            文章檔案(85)

            搜索

            最新評論

            • 1.?re: poj1426
            • 我嚓,,輝哥,,居然搜到你的題解了
            • --season
            • 2.?re: poj3083
            • @王私江
              (8+i)&3 相當于是 取余3的意思 因為 3 的 二進制是 000011 和(8+i)
            • --游客
            • 3.?re: poj3414[未登錄]
            • @王私江
              0ms
            • --jh818012
            • 4.?re: poj3414
            • 200+行,跑了多少ms呢?我的130+行哦,你菜啦,哈哈。
            • --王私江
            • 5.?re: poj1426
            • 評論內容較長,點擊標題查看
            • --王私江
            久久香蕉国产线看观看精品yw| 亚洲综合伊人久久大杳蕉| 久久国产高清字幕中文| 久久亚洲国产欧洲精品一| 韩国三级中文字幕hd久久精品| 国产99久久久国产精免费| 综合久久一区二区三区 | 国产精品免费久久| 久久这里有精品视频| 欧美一区二区三区久久综| 久久精品夜色噜噜亚洲A∨| 久久久国产99久久国产一| 国产精品无码久久综合| 色偷偷88欧美精品久久久| 精品国产乱码久久久久久郑州公司| 99久久国产主播综合精品| 99久久国产精品免费一区二区| 久久亚洲高清观看| 无遮挡粉嫩小泬久久久久久久| 久久精品无码一区二区三区免费| 色婷婷综合久久久久中文| 日产久久强奸免费的看| 999久久久无码国产精品| 99久久综合国产精品免费| 99久久精品费精品国产| 国产Av激情久久无码天堂| 国产精品美女久久福利网站| 精品久久久久久久久久久久久久久 | 久久久国产精品福利免费| 国产69精品久久久久APP下载| 欧美久久精品一级c片片| 漂亮人妻被黑人久久精品| 国内精品伊人久久久久777| 亚洲Av无码国产情品久久| 国产精品久久久久一区二区三区| 99久久免费国产精精品| 久久丫精品国产亚洲av不卡| 无码国内精品久久人妻| 久久精品国产第一区二区三区| 午夜久久久久久禁播电影| 久久精品毛片免费观看|