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

隨筆 - 87  文章 - 279  trackbacks - 0
<2010年5月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

潛心看書研究!

常用鏈接

留言簿(19)

隨筆分類(81)

文章分類(89)

相冊(cè)

ACM OJ

My friends

搜索

  •  

積分與排名

  • 積分 - 219408
  • 排名 - 118

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

寫了個(gè)比較通用的堆,可直接用作優(yōu)先隊(duì)列

Silver Cow Party
Time Limit:2000MS  Memory Limit:65536K
Total Submit:1112 Accepted:326

Description

One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ XN). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires Ti (1 ≤ Ti ≤ 100) units of time to traverse.

Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow's return route might be different from her original route to the party since roads are one-way.

Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?

 

Input
Line 1: Three space-separated integers, respectively: N, M, and X
Lines 2..M+1: Line i+1 describes road i with three space-separated integers: Ai, Bi, and Ti. The described road runs from farm Ai to farm Bi, requiring Ti time units to traverse.

Output
Line 1: One integer: the maximum of time any one cow must walk.

Sample Input

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

 

Sample Output

10

 

Hint
Cow 4 proceeds directly to the party (3 units) and returns via farms 1 and 3 (7 units), for a total of 10 time units.

Source
USACO 2007 February Silver



#include <iostream>
using namespace std;

const int INF = 1 << 28;

int adj[1001][1001], adjw[1001][1001], na[1001];
int n, m, x;


//heap sink,swim,getmin,insert參數(shù)均為外部編號(hào),wt為其權(quán)值
int heap[100001], id[100001], hsize;
int *key;
void init(int s, int *wt) {
    
int i;
    hsize 
= s; 
    key 
= wt;
    
for (i=1; i<=hsize; i++{
        heap[i] 
= i;
        id[i] 
= i;
    }

}

void swim(int u) {
    
int p = id[u], q = p >> 1, ku = key[u];
    
while (q && ku < key[heap[q]]) {
        id[heap[q]] 
= p;
        heap[p] 
= heap[q];
        p 
= q;
        q 
= p >> 1;
    }

    id[u] 
= p;
    heap[p] 
= u;
}

void sink(int u) {
    
int p = id[u],q = p << 1, ku = key[u];
    
while (q <= hsize) {
        
if (q < hsize && key[heap[q+1]] < key[heap[q]]) q++;
        
if (key[heap[q]] >= ku) break;
        id[heap[q]] 
= p;
        heap[p] 
= heap[q];
        p 
= q; 
        q 
= p << 1;
    }

    id[u] 
= p;
    heap[p] 
= u;
}

int getmin() {
    
int ret = heap[1];
    id[ret] 
= -1;
    id[heap[hsize]] 
= 1;
    heap[
1= heap[hsize];
    hsize
--;
    sink(heap[
1]);
    
return ret;
}

void insert(int u) {
    heap[
++hsize] = u;
    id[u] 
= hsize;
    swim(u);
}

void build() {
    
int i;
    
for (i=hsize/2; i>0; i--) sink(heap[i]);
}

bool isEmpty() {
    
return hsize == 0;
}

int dijkstraHeap(int beg, int end=-1{
    
int i, j, k, u, v, w;
    
int dist[1001], chk[1001];
    
for (i=1; i<=n; i++{
        dist[i] 
= INF;
        chk[i] 
= 0;
    }

    init(n, dist);
    dist[beg] 
= 0; swim(beg);
    
while (!isEmpty()) {
        u 
= getmin();
        
if (u == end) break;
        chk[u] 
= 1;
        
for (i=0; i<na[u]; i++{
            v 
= adj[u][i];
            w 
= adjw[u][i];
            
if (dist[v] > dist[u] + w) {
                dist[v] 
= dist[u] + w;
                swim(v);
            }

        }

    }

    
if (end == -1return dist[n];
    
return dist[end];
}


int main() {
    
int i, j, k, u, v, w;
    
int val[1001];
    scanf(
"%d%d%d"&n, &m, &x);
    
for (i=0; i<m; i++{
        scanf(
"%d%d%d"&u, &v, &w);
        adj[u][na[u]] 
= v; 
        adjw[u][na[u]] 
= w;
        na[u]
++;
    }

   
    dijkstraHeap(x);
    memcpy(val, key, 
sizeof(val));
    
    
int ans = 0;
    
for (i=1; i<=n; i++{
        
int tmp = dijkstraHeap(i,x);
        
if (tmp+val[i] > ans) ans = tmp + val[i];
    }

    
    printf(
"%d\n", ans);
    
return 0;
}
posted on 2007-07-23 20:51 閱讀(1300) 評(píng)論(4)  編輯 收藏 引用 所屬分類: 數(shù)據(jù)結(jié)構(gòu)與算法ACM題目

FeedBack:
# re: pku3268 dij+heap 2007-07-27 08:41 oyjpart
終于更新blog了。。。  回復(fù)  更多評(píng)論
  
# re: pku3268 dij+heap 2007-08-01 20:29 relic
不必n次dijkstra,只要把所有邊反向,再來一次dijkstra就可以了。算上第一次一共兩次dij  回復(fù)  更多評(píng)論
  
# re: pku3268 dij+heap 2007-08-03 22:58 
偷懶了:)  回復(fù)  更多評(píng)論
  
# re: pku3268 dij+heap 2007-09-18 13:16 drizzlecrj
@relic
re  回復(fù)  更多評(píng)論
  
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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| 久久激情五月激情| 国产欧美精品一区aⅴ影院| 亚洲欧美精品suv| 欧美freesex8一10精品| 久久在线免费视频| 亚洲国产综合在线看不卡| 欧美国产精品久久| 蜜月aⅴ免费一区二区三区| 国产精品在线看| 欧美在线视频免费| 久久久精品国产一区二区三区| 狠狠噜噜久久| 免费成人在线观看视频| 免费观看一级特黄欧美大片| 国产嫩草影院久久久久| 性欧美xxxx大乳国产app| 亚洲欧美日韩另类精品一区二区三区| 国产精品乱看| 欧美一级久久| 久久精品九九| 日韩视频第一页| 一区二区三区欧美在线| 国产精品久久久亚洲一区| 久久久久久久成人| 欧美99在线视频观看| 亚洲一区二区三区四区中文| 午夜视频一区二区| 最近中文字幕日韩精品| 亚洲乱码视频| 国产一区二区三区高清| 欧美激情按摩| 国产精品婷婷午夜在线观看| 欧美成人在线影院| 国产精品福利在线观看网址| 久久一本综合频道| 欧美日韩国产美| 久久一二三区| 欧美日韩中文| 欧美福利视频网站| 国产精品实拍| 亚洲国产精品国自产拍av秋霞| 欧美日韩亚洲国产精品| 久久综合免费视频影院| 欧美国产精品一区| 亚洲午夜精品福利| 狂野欧美激情性xxxx欧美| 亚洲欧美日韩国产综合| 久久伊人精品天天| 一区二区三区日韩欧美| 久久嫩草精品久久久精品| 亚洲私人影院在线观看| 欧美a级一区二区| 久久久精品久久久久| 男男成人高潮片免费网站| 欧美在线免费观看| 欧美丝袜第一区| 欧美电影在线观看完整版| 国产亚洲午夜| 亚洲欧美日韩专区| 亚洲一级在线观看| 欧美日本亚洲视频| 亚洲高清久久久| 激情婷婷久久| 久久gogo国模裸体人体| 欧美一二三视频| 欧美日韩视频一区二区| 亚洲第一偷拍| 亚洲高清激情| 美日韩精品免费| 美女任你摸久久| 国内自拍一区| 亚洲一区二区三区视频| 亚洲欧美精品在线| 国产精品视频免费观看| 在线综合亚洲欧美在线视频| 在线亚洲高清视频| 欧美另类久久久品| 亚洲人成在线观看一区二区| 亚洲裸体视频| 欧美日韩另类综合| 艳妇臀荡乳欲伦亚洲一区| 亚洲天堂免费观看| 国产精品福利影院| 亚洲欧美在线免费| 久久精品国产v日韩v亚洲 | 狂野欧美激情性xxxx欧美| 国产一区美女| 久久久水蜜桃av免费网站| 久久精品最新地址| 香蕉乱码成人久久天堂爱免费| 亚洲一区二区在线播放| 国产日韩欧美综合一区| 每日更新成人在线视频| 一区二区欧美日韩| 美女免费视频一区| 亚洲女爱视频在线| 一区二区在线观看视频| 欧美二区在线播放| 午夜精品婷婷| 亚洲日本中文字幕| 久久精品国产久精国产思思| 亚洲精品久久久久久久久久久| 国产精品久久久久久久久借妻| 久久久之久亚州精品露出| aa级大片欧美三级| 欧美粗暴jizz性欧美20| 午夜激情综合网| 亚洲精品小视频| 韩日成人av| 国产精品一级久久久| 男女激情久久| 久久久夜夜夜| 小处雏高清一区二区三区| 日韩小视频在线观看专区| 老司机精品视频网站| 性8sex亚洲区入口| 中文国产一区| 日韩网站在线看片你懂的| 国内精品伊人久久久久av一坑| 欧美性猛交99久久久久99按摩| 免费成年人欧美视频| 久久久之久亚州精品露出| 西瓜成人精品人成网站| 亚洲一区二区三区免费在线观看| 亚洲丶国产丶欧美一区二区三区| 久久蜜桃资源一区二区老牛 | 亚洲电影中文字幕| 国产有码一区二区| 国产日韩一区在线| 国产日韩欧美一区| 国产久一道中文一区| 国产精品家教| 国产精品乱看| 国产精品一二三视频| 国产精品亚洲一区二区三区在线| 欧美午夜片在线观看| 欧美日韩精品一区视频| 欧美日韩中文精品| 国产精品久久久久久福利一牛影视| 欧美性开放视频| 国产精品va在线| 国产精品久久91| 国产精品一区二区三区久久久| 国产精品社区| 国产亚洲毛片在线| 在线成人av.com| 91久久久亚洲精品| 亚洲最新视频在线| 亚洲性av在线| 性欧美激情精品| 久久综合网hezyo| 亚洲二区在线视频| 日韩小视频在线观看专区| 亚洲永久精品国产| 欧美亚洲专区| 久久午夜视频| 欧美日韩国产成人在线91| 国产精品99一区二区| 国产日本精品| 亚洲国产精品尤物yw在线观看 | 国产精品中文字幕欧美| 韩国一区二区三区美女美女秀| 影音先锋亚洲一区| 99国产精品久久久久老师| 亚洲欧美成人综合| 麻豆精品精华液| 亚洲精品看片| 欧美一区二区三区免费视| 免费亚洲婷婷| 国产精品一卡二卡| 91久久综合| 欧美在线日韩在线| 欧美激情一二三区| 亚洲综合精品| 欧美激情国产高清| 国产亚洲va综合人人澡精品| 亚洲精品久久久久久一区二区| 亚洲欧美日韩在线| 欧美韩日亚洲| 香蕉久久夜色精品| 欧美日韩国产综合新一区| 黑人巨大精品欧美一区二区小视频 | 国产精品亚洲第一区在线暖暖韩国| 在线观看亚洲视频啊啊啊啊| 亚洲天天影视| 欧美激情视频免费观看| 亚洲欧美日韩精品久久亚洲区 | 亚洲人成网站精品片在线观看| 亚洲自拍偷拍色片视频| 欧美国产日韩xxxxx| 亚洲男女自偷自拍| 欧美日韩一区在线播放| 亚洲国产精品高清久久久| 欧美在线精品一区| 亚洲无吗在线| 欧美日韩亚洲综合一区| 91久久在线播放|