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

T9的空間

You will never walk alone!

  C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
  69 隨筆 :: 0 文章 :: 28 評論 :: 0 Trackbacks
http://acm.pku.cn/JudgeOnline/problem?id=1511
兩個圖,spfa正向求一次,反向求一次
#include<iostream>
#include
<algorithm>
#include
<queue>

using namespace std;

const int Nmax=1000001;
const int oo=0x7fffffff;

typedef 
struct node
{
    
int next;
    
int e;
    
int w;
}
node;

int dis[Nmax];
node g[Nmax];
node reg[Nmax];
int p[Nmax];
int rep[Nmax];

queue
<int>q;
bool usd[Nmax];
int i,j,k;

int Min[Nmax];

void SPFA(node g[],int p[])
{
    
while(!q.empty ()) q.pop();
    memset(usd,
false,sizeof(usd));
    memset(dis,
0x7f,sizeof(dis));
    q.push(
1); dis[1]=0;
    usd[
1]=true;
    
while(!q.empty())
    
{
        
int tmp=q.front ();
        q.pop();
        
for(j=p[tmp];j!=-1;j=g[j].next)
        
{
            
if(dis[tmp]<oo&&dis[tmp]+g[j].w<dis[g[j].e])
            
{
                dis[g[j].e]
=dis[tmp]+g[j].w;
                
if(!usd[g[j].e]) 
                
{
                    q.push(g[j].e);
                    usd[g[j].e]
=true;
                }

            }

        }

    }

}



int main()
{
    
int P,Q;
    
int cas;
    scanf(
"%d",&cas);
    
while(cas--)
    
{
        scanf(
"%d%d",&P,&Q);
        
int from,to,cost;
        
int cnt=0,cnt1=0;
        memset(p,
-1,sizeof(p));
        memset(rep,
-1,sizeof(rep));
        
for(i=1;i<=Q;i++)
        
{
            scanf(
"%d%d%d",&from,&to,&cost);
            g[cnt].next
=p[from];
            g[cnt].e
=to;
            g[cnt].w
=cost;
            p[from]
=cnt++;

            reg[cnt1].next
=rep[to];
            reg[cnt1].e
=from;
            reg[cnt1].w
=cost;
            rep[to]
=cnt1++;
        }

        SPFA(g,p);
        memcpy(Min,dis,
sizeof(dis));
        SPFA(reg,rep);
        
for(i=1;i<=P;i++)
             Min[i]
+=dis[i];
        __int64 re
=0;
        
for(i=2;i<=P;i++)
             re
+=Min[i];
        printf(
"%I64d\n",re);
    }

    
return 0;
}

posted on 2008-09-12 11:17 Torres 閱讀(514) 評論(0)  編輯 收藏 引用 所屬分類: Graph
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲精品九九| 久久av一区二区三区漫画| 亚洲精品一二三| 欧美大片免费久久精品三p| 久久蜜桃资源一区二区老牛| 欧美一区1区三区3区公司| 亚洲综合国产激情另类一区| 亚洲欧美中文日韩在线| 欧美一区二区三区电影在线观看 | 欧美日韩dvd在线观看| 暖暖成人免费视频| 国产精品一区免费观看| 原创国产精品91| 亚洲一区二区三区777| 欧美在线免费观看亚洲| 久久久人人人| 欧美国产一区在线| 亚洲精品一区在线观看| 亚洲一线二线三线久久久| 亚洲日韩欧美视频一区| 亚洲欧美激情诱惑| 亚洲国产高清视频| 亚洲视频精品| 欧美日韩成人在线观看| 亚洲黄一区二区| 久热精品视频在线观看| 亚洲欧美春色| 国产喷白浆一区二区三区| 日韩小视频在线观看专区| 久久综合激情| 欧美一区二区三区日韩视频| 国产精品福利av| 亚洲男人的天堂在线| 99热精品在线| 欧美日本高清视频| 亚洲性视频h| 亚洲一级一区| 国产亚洲午夜| 亚洲国产精品精华液2区45| 亚洲欧美日韩国产精品| 亚洲美女尤物影院| 亚洲国产黄色片| 久久久久久穴| 久久人体大胆视频| 国产小视频国产精品| 午夜在线观看欧美| 国产毛片一区| 正在播放亚洲| 久久久午夜视频| 一区二区冒白浆视频| 亚洲国产精品一区二区久| 久久久精品国产一区二区三区| 亚洲第一伊人| 亚洲一级黄色av| 久久久久久97三级| 夜夜爽99久久国产综合精品女不卡 | 中文久久乱码一区二区| 韩国欧美一区| 亚洲欧美日韩另类| 亚洲欧美日韩国产一区二区三区 | 久久一区二区三区av| 欧美日产国产成人免费图片| 麻豆成人av| 亚洲福利一区| 噜噜噜久久亚洲精品国产品小说| 亚洲欧美成人一区二区三区| 美女福利精品视频| 亚洲高清不卡| 亚洲精一区二区三区| 你懂的视频一区二区| 麻豆91精品91久久久的内涵| 激情av一区| 免费日韩av| 亚洲精品综合在线| 一区二区av在线| 国产精品视频网| 久久久久久久激情视频| 亚洲高清毛片| 亚洲欧美在线视频观看| 国内精品久久久| 久久久久久9| 久久久精品国产免费观看同学| 国产精品自拍一区| 久久亚洲精品一区二区| 日韩视频免费在线观看| 欧美尤物一区| 亚洲精品免费在线| 国产日韩欧美一区二区三区在线观看 | 欧美一站二站| 亚洲国产天堂网精品网站| 欧美影片第一页| 亚洲人成毛片在线播放| 黄色免费成人| 国内久久精品| 国产欧美精品在线观看| 国产精品黄色| 国产欧美一区二区视频| 欧美xart系列高清| 亚洲欧美日韩一区二区在线 | 欧美日产在线观看| 久久伊人免费视频| 欧美在线电影| 久久久久亚洲综合| 你懂的国产精品永久在线| 欧美黑人多人双交| 亚洲图色在线| 亚洲精品久久久久久久久久久久久| 亚洲一区二区高清| 亚洲天堂视频在线观看| 欧美一区二区三区在线免费观看| 黄色亚洲大片免费在线观看| 欧美噜噜久久久xxx| 美女啪啪无遮挡免费久久网站| 久久国产精品一区二区三区四区| 亚洲一级一区| 亚洲中午字幕| 久久久水蜜桃av免费网站| 久久久久国内| 欧美日韩在线直播| 免费欧美电影| 亚洲国产mv| 中日韩男男gay无套| 午夜久久久久久| 欧美 日韩 国产一区二区在线视频 | 亚洲综合第一| 久久天天躁狠狠躁夜夜爽蜜月 | 亚洲巨乳在线| 在线中文字幕日韩| 欧美主播一区二区三区| 欧美激情亚洲精品| 亚洲欧美一区二区原创| 免费欧美电影| 一区二区三区在线免费播放| 亚洲视频一区二区在线观看 | 西西人体一区二区| 欧美国产一区二区三区激情无套| 国产日韩欧美高清| 亚洲图片欧美一区| 99精品欧美一区| 欧美日韩免费| 一级成人国产| 99视频一区二区| 免费不卡视频| 亚洲国产婷婷香蕉久久久久久| 久久精品一区二区三区中文字幕| 先锋a资源在线看亚洲| 欧美性开放视频| 夜夜嗨av色一区二区不卡| 亚洲电影激情视频网站| 欧美高清视频一二三区| 夜夜夜久久久| 一本一道久久综合狠狠老精东影业 | 亚洲视频 欧洲视频| 欧美日韩午夜在线视频| 一区二区三区欧美在线| 99v久久综合狠狠综合久久| 国产精品高潮视频| 狂野欧美性猛交xxxx巴西| 你懂的视频一区二区| 亚洲免费人成在线视频观看| 一区二区三区久久久| 国产日韩亚洲欧美综合| 欧美激情国产日韩精品一区18| 欧美精品在线观看| 久久精品盗摄| 老司机午夜免费精品视频| 久久精品在线观看| 一区二区三区精品在线| 久久精品91久久香蕉加勒比| 亚洲精品日本| 久久超碰97人人做人人爱| 日韩视频免费在线观看| 欧美在线视频在线播放完整版免费观看 | 亚洲黄色免费网站| 国产精品亚洲综合天堂夜夜| 亚洲激情av| 亚洲三级影院| 欧美成人精品福利| 猫咪成人在线观看| 国产综合精品一区| 一本色道久久综合亚洲精品不| 亚洲激情网站| 在线播放一区| 亚洲免费精品| 亚洲国产精品成人久久综合一区| 亚洲制服av| 欧美一区国产二区| 欧美精品日日鲁夜夜添| 亚洲高清二区| 一卡二卡3卡四卡高清精品视频| 欧美成人网在线| 亚洲免费播放| 一区二区三区日韩在线观看| 亚洲欧美日韩国产综合| 欧美精品日韩一区| 久久激情久久| 欧美日韩精品免费在线观看视频| 美女诱惑一区| 国产一区二区三区最好精华液| 久久久精品国产免大香伊 |