• <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>
            #include? < iostream >
            #include?
            < vector >

            using ? namespace ?std;

            struct ?Edge{
            ????
            int ?u,?v,?w;
            ????Edge(?
            int ?a = ? 0 ,? int ?b = ? 0 ,? int ?c = ? 0 ?):
            ????????u(a),?v(b),?w(c)?{}
            };

            int ?n,?m;
            int ?c[ 1010 ],?sum[ 1010 ],?dist[ 1010 ];
            vector
            < Edge > ?ege;

            bool ?bellman(){
            ????memset(?dist,?
            0 ,? sizeof (dist)?);????
            ????
            int ?len = ?ege.size();
            ????
            for (? int ?i = ? 0 ;?i < ?n;? ++ i?){
            ????????
            for (? int ?j = ? 0 ;?j < ?len;? ++ j?)
            ????????
            if (?dist[?ege[j].u?] + ?ege[j].w < ?dist[?ege[j].v?]?)
            ????????dist[?ege[j].v?]
            = ?dist[?ege[j].u?] + ?ege[j].w;
            ????}
            ????
            bool ?flag = ? false ;
            ????
            for (? int ?j = ? 0 ;?j < ?len;? ++ j?)
            ????
            if (?dist[?ege[j].u?] + ?ege[j].w < ?dist[?ege[j].v?]?)
            ????
            return ? false ;
            ????
            ????
            return ? true ;
            }

            int ?main(){
            ????
            while (?scanf( " %d%d " , & n, & m) != ?EOF?){
            ????????memset(?sum,?
            0 ,? sizeof (sum)?);
            ????????
            for (? int ?i = ? 1 ;?i <= ?n;? ++ i?){
            ?????????????scanf(
            " %d " ,?c + ?i?);
            ?????????????sum[i]
            = ?sum[i - 1 ] + ?c[i];
            ?????????????ege.push_back(?Edge(?i
            - 1 ,?i,?c[i]?)?);
            ?????????????ege.push_back(?Edge(?i,?i
            - 1 ,? 0 ?)?);
            ????????}
            ????????
            int ?u,?v,?w;
            ????????
            while (?m -- ?){
            ????????????scanf(
            " %d%d%d " , & u, & v, & w?);
            ????????????u
            -- ;
            ????????????ege.push_back(?Edge(?v,?u,?
            - w?)?);
            ????????????ege.push_back(?Edge(?u,?v,?sum[v]
            - ?sum[u]?)?);
            ????????}
            ????????
            if (? ! bellman()?)?puts( " Bad?Estimations " );
            ????????
            else ?????????????printf( " %d\n " ,dist[n] - ?dist[ 0 ]?);
            ????????
            ????????ege.clear();
            ????}
            ????
            ????
            return ? 0 ;
            }
            posted on 2009-07-11 15:32 Darren 閱讀(424) 評論(0)  編輯 收藏 引用 所屬分類: 數據結構
            久久久久亚洲av无码专区| 中文字幕久久亚洲一区| 亚洲va久久久噜噜噜久久狠狠 | 色综合久久久久网| 久久九色综合九色99伊人| 久久精品国产亚洲Aⅴ蜜臀色欲| 久久久久久精品免费免费自慰| 久久亚洲精品成人AV| 久久精品国产福利国产琪琪| 久久精品国产色蜜蜜麻豆| 国产成人无码精品久久久免费| 2021久久精品免费观看| Xx性欧美肥妇精品久久久久久| 久久人妻少妇嫩草AV蜜桃| 亚洲成人精品久久| 97久久精品无码一区二区| 欧美久久一区二区三区| 日本免费久久久久久久网站| 久久精品国产2020| 久久91精品综合国产首页| jizzjizz国产精品久久| 99蜜桃臀久久久欧美精品网站 | 99久久免费国产精品| 久久精品无码一区二区无码| 污污内射久久一区二区欧美日韩| 国产真实乱对白精彩久久| 精品久久久久久中文字幕人妻最新| 伊人 久久 精品| 色欲综合久久躁天天躁| 久久精品国产一区二区电影| 成人午夜精品久久久久久久小说| 久久九九全国免费| 国内精品久久国产大陆| 欧美一区二区三区久久综| 日韩AV无码久久一区二区| 久久人人爽人人人人爽AV| 久久久久亚洲AV成人网人人网站| 亚洲?V乱码久久精品蜜桃| 久久99热这里只频精品6| 99久久国产综合精品女同图片| 久久精品人人做人人爽电影|