青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

枯葉北風寒,忽然年以殘,念往昔,語默心酸。二十光陰無一物,韶光賤,寐難安; 不畏形影單,道途阻且慢,哪曲折,如渡飛湍。斬浪劈波酬壯志,同把酒,共言歡! -如夢令

HDOJ 3592 World Exhibition——差分約束

最短路中,求出源到各點的最短路。如果a->b有一條邊,那么dis[a]+w(a,b)>=dis[b].
將所有的條件轉化成邊即可。

#include<iostream>
#include
<algorithm>
#include
<cmath>
#include
<queue>
using namespace std;
const int maxn=1010;
const int maxm=1000000;
const int INF=1000000000;
struct node
{
    
int t;
    
int w;
    node 
*next;
}
edge[maxm],*adj[maxn];

int len=0;
void init(int n)
{
    
for(int i=0;i<n;i++)
        adj[i]
=NULL;
    len
=0;
}


void addedge(int u,int v,int w)
{
    edge[len].t
=v;edge[len].w=w;edge[len].next=adj[u];adj[u]=&edge[len++];
}


int dis[maxn];//[0,n-1]
int use[maxn];
int cnt[maxn];
bool SPFA(int n,int s)
{
    queue
<int>Q;
    fill(dis,dis
+n,INF);
    fill(use,use
+n,0);
    fill(cnt,cnt
+n,0);
    dis[s]
=0;
    use[s]
=1;
    Q.push(s);
    
while(!Q.empty())
    
{
        
int x=Q.front();Q.pop();
        use[x]
=0;
        
++cnt[x];
        
if(cnt[x]>n)return false;
        
for(node *p=adj[x];p;p=p->next)
        
{
            
int t=p->t,w=p->w;
            
if(dis[x]+w<dis[t])
            
{
                dis[t]
=dis[x]+w;
                
if(!use[t])
                
{
                    Q.push(t);
                    use[t]
=1;
                }

            }

        }


    }

    
return true;
}


int main()
{
    
int ca;
    scanf(
"%d",&ca);
    
while(ca--)
    
{
        
        
int n,x,y;
        scanf(
"%d%d%d",&n,&x,&y);
        init(n);
        
for(int i=0;i<x;i++)
        
{
            
int a,b,c;
            scanf(
"%d%d%d",&a,&b,&c);
            a
--;b--;
            addedge(a,b,c);
        }

        
for(int i=0;i<y;i++)
        
{
            
int a,b,c;
            scanf(
"%d%d%d",&a,&b,&c);
            a
--;b--;
            addedge(b,a,
-c);
        }

        
//for(int i=0;i<n-1;i++)
        
//    addedge(i+1,i,0);
        if(!SPFA(n,0))printf("-1\n");
        
else if(dis[n-1]==INF)printf("-2\n");
        
else printf("%d\n",dis[n-1]);


    }



    
return 0;
}

posted on 2010-11-15 15:09 abilitytao 閱讀(297) 評論(0)  編輯 收藏 引用

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产在线乱码一区二区三区| 欧美肥婆在线| 国产模特精品视频久久久久| 欧美一区二区三区免费观看| 午夜精品久久久久久久99热浪潮| 国产精品一二三视频| 久久免费偷拍视频| 免费在线播放第一区高清av| 中文高清一区| 欧美一区二区视频在线观看2020| 亚洲第一在线| 亚洲午夜电影网| 怡红院精品视频| 亚洲精品国产日韩| 国产精品香蕉在线观看| 美国成人直播| 欧美肉体xxxx裸体137大胆| 欧美伊人久久久久久久久影院| 久久频这里精品99香蕉| 中文欧美在线视频| 久久久91精品| 亚洲综合清纯丝袜自拍| 狼人天天伊人久久| 香港久久久电影| 欧美www视频在线观看| 亚洲一区视频在线观看视频| 久久精品盗摄| 亚洲欧美精品伊人久久| 免费观看亚洲视频大全| 亚久久调教视频| 欧美激情亚洲激情| 久久网站免费| 国产精品毛片| 99国产精品久久久久久久成人热| 国内外成人在线| 99国产一区| 亚洲日本中文字幕| 久久久久久久精| 久久gogo国模裸体人体| 欧美三级日本三级少妇99| 欧美激情欧美狂野欧美精品| 国产精品自拍一区| 一本色道久久综合亚洲91| 最近中文字幕日韩精品| 久久久91精品国产| 久久国产精品亚洲77777| 精品二区久久| 国产精品色午夜在线观看| 亚洲小少妇裸体bbw| 久久中文字幕一区二区三区| 亚洲一区二三| 欧美日韩在线不卡一区| 亚洲激情中文1区| 亚洲第一福利社区| 久久久久久网站| 久久久国产一区二区| 国产精品日韩在线观看| 亚洲夜间福利| 亚洲免费一在线| 欧美日韩在线观看视频| 亚洲精品五月天| 亚洲视频在线免费观看| 欧美日韩国产成人在线观看| 亚洲日本在线观看| 亚洲视频在线观看一区| 国产精品户外野外| 亚洲主播在线播放| 久久精品亚洲精品| 一区二区三区在线观看国产| 久久国产精品久久精品国产| 久久影院午夜片一区| 一区久久精品| 久久综合伊人77777| 亚洲国产精品精华液2区45| 日韩视频国产视频| 欧美视频精品在线| 小处雏高清一区二区三区| 久久久水蜜桃| 亚洲精品欧美精品| 国产精品久久久久久一区二区三区 | 欧美午夜电影完整版| 亚洲一区二区三区免费在线观看| 午夜激情久久久| 国产综合网站| 欧美福利视频| 中文亚洲免费| 欧美1区2区| 夜夜爽www精品| 国产免费成人在线视频| 麻豆9191精品国产| 一区二区三区免费看| 久久久一区二区| 亚洲精品中文在线| 国产免费成人av| 免费亚洲电影在线| 亚洲欧美另类在线观看| 欧美激情精品久久久久久大尺度| 亚洲视频在线观看免费| 精品成人一区二区三区| 欧美激情一二三区| 午夜欧美不卡精品aaaaa| 欧美黑人国产人伦爽爽爽| 亚洲一区二区综合| 最近看过的日韩成人| 国产日韩在线播放| 欧美精品一卡二卡| 久久久精品午夜少妇| 在线午夜精品| 亚洲电影第三页| 久久福利电影| 欧美激情视频一区二区三区免费| 国产精品第十页| 一区二区三区久久精品| 理论片一区二区在线| 亚洲已满18点击进入久久| 怡红院av一区二区三区| 国产精品日韩欧美| 欧美欧美天天天天操| 久久性天堂网| 午夜欧美大片免费观看 | 国产精品自在欧美一区| 欧美成人综合在线| 久久精品毛片| 亚洲欧美激情四射在线日 | 欧美波霸影院| 久久精品午夜| 亚欧美中日韩视频| 亚洲欧美第一页| 中文日韩电影网站| 99国产精品私拍| 亚洲精品国产系列| 亚洲精品国产精品国自产观看浪潮| 精品91久久久久| 国内精品久久久久影院优| 国产精品自拍一区| 国产欧美一区二区精品婷婷| 国产精品九九| 国产精品欧美精品| 国产精品白丝jk黑袜喷水| 欧美日韩一区视频| 欧美日韩视频| 国产精品久久99| 国产精品自拍网站| 韩国成人福利片在线播放| 国产一区高清视频| 伊人激情综合| 亚洲国产另类久久精品| 亚洲激情视频网| 一本大道久久a久久综合婷婷| 亚洲毛片在线观看| 9色精品在线| 午夜久久久久久| 久久在线播放| 亚洲国产精品一区二区三区 | 亚洲一区二区久久| 午夜精品理论片| 久久精品视频网| 欧美国产视频日韩| 亚洲精品国产精品国自产观看浪潮| 亚洲人人精品| 午夜精品国产更新| 久久嫩草精品久久久精品| 欧美国产视频日韩| 国产精品激情偷乱一区二区∴| 国产日韩综合一区二区性色av| 国语精品中文字幕| 亚洲另类一区二区| 午夜性色一区二区三区免费视频| 欧美主播一区二区三区| 麻豆国产va免费精品高清在线| 亚洲电影第三页| 亚洲在线一区| 蜜桃av综合| 国产人成一区二区三区影院| 在线观看亚洲一区| 亚洲一区在线播放| 美女精品在线观看| 亚洲视频中文| 男女激情视频一区| 国产欧美日韩精品一区| 91久久在线| 久久精品一区| 亚洲精品视频免费在线观看| 欧美日韩日日骚| 伊人久久成人| 午夜精品久久久久久| 亚洲经典自拍| 久久精品99| 一区二区三区四区精品| 一区二区三区欧美在线观看| 欧美一区国产在线| 国产精品成人观看视频国产奇米| 在线观看日韩av| 欧美一区二区三区视频免费播放| 欧美激情一区二区三区蜜桃视频| 亚洲欧美日韩专区| 欧美午夜精品一区| 一本久道综合久久精品| 免费观看日韩| 欧美专区在线|