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

隨筆 - 87  文章 - 279  trackbacks - 0
<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

潛心看書研究!

常用鏈接

留言簿(19)

隨筆分類(81)

文章分類(89)

相冊

ACM OJ

My friends

搜索

  •  

積分與排名

  • 積分 - 219404
  • 排名 - 118

最新評論

閱讀排行榜

評論排行榜

寫了個(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ù)均為外部編號,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) 評論(4)  編輯 收藏 引用 所屬分類: 數(shù)據(jù)結(jié)構(gòu)與算法 、ACM題目

FeedBack:
# re: pku3268 dij+heap 2007-07-27 08:41 oyjpart
終于更新blog了。。。  回復(fù)  更多評論
  
# re: pku3268 dij+heap 2007-08-01 20:29 relic
不必n次dijkstra,只要把所有邊反向,再來一次dijkstra就可以了。算上第一次一共兩次dij  回復(fù)  更多評論
  
# re: pku3268 dij+heap 2007-08-03 22:58 
偷懶了:)  回復(fù)  更多評論
  
# re: pku3268 dij+heap 2007-09-18 13:16 drizzlecrj
@relic
re  回復(fù)  更多評論
  
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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| 免费观看日韩av| 狠狠色丁香婷婷综合| 欧美一级专区免费大片| 欧美一区免费视频| 国产精品美女在线| 亚洲自拍偷拍网址| 先锋影音网一区二区| 国产精品手机在线| 亚洲伊人网站| 欧美呦呦网站| 国产午夜精品视频| 久久成人资源| 欧美成人在线免费观看| 亚洲国产女人aaa毛片在线| 久久一区免费| 亚洲国产成人不卡| 一二三区精品| 国产精品久久久久久久9999| 国产精品99久久不卡二区| 性色av一区二区怡红| 国产欧美在线看| 久久精品国产亚洲一区二区| 免费久久精品视频| 一本色道久久综合狠狠躁篇的优点 | 亚洲激情在线视频| 欧美精品系列| 亚洲欧美日韩中文播放| 久久久久久穴| 亚洲日本电影| 国产精品免费网站| 久久综合给合| 99精品国产热久久91蜜凸| 香蕉久久夜色| 影音先锋日韩有码| 欧美日韩视频在线| 欧美在线日韩在线| 亚洲国产精品女人久久久| 亚洲专区一区| 影音先锋日韩资源| 欧美午夜影院| 久久天天躁狠狠躁夜夜av| 91久久久久久久久久久久久| 午夜免费久久久久| 亚洲高清视频一区二区| 欧美午夜一区二区| 狼人社综合社区| 一区二区高清视频| 麻豆精品视频在线观看视频| 一区二区精品国产| 伊人久久亚洲影院| 国产精品久线观看视频| 久久夜色精品国产| 亚洲伊人观看| 亚洲精品一区二区网址| 久久久av水蜜桃| 亚洲性感美女99在线| 在线观看一区| 国产午夜精品一区二区三区视频 | 欧美一级淫片播放口| 最新69国产成人精品视频免费| 国产精品国产a| 欧美激情1区2区3区| 久久精品视频导航| 亚洲视频一区二区| 亚洲激情在线视频| 免费成人美女女| 久久黄色影院| 亚洲欧美激情诱惑| aa级大片欧美三级| 亚洲欧洲午夜| 黄色成人小视频| 国产日韩成人精品| 国产精品高清免费在线观看| 欧美激情一区二区在线| 久久久久国产免费免费| 亚洲尤物精选| 亚洲天堂成人在线观看| 亚洲精品久久久久久久久久久久| 免费久久99精品国产自在现线| 久久精品视频在线免费观看| 欧美一级片一区| 午夜在线不卡| 午夜精品短视频| 亚洲欧美日韩中文在线制服| 亚洲一级高清| 在线一区亚洲| 亚洲网站在线播放| 亚洲一区二区三区在线视频| 亚洲最快最全在线视频| 亚洲精品在线视频| 一本一本a久久| 中日韩高清电影网| 亚洲一区在线观看视频| 亚洲欧美日韩另类精品一区二区三区 | 亚洲欧美www| 先锋影音网一区二区| 欧美自拍丝袜亚洲| 久久久久久有精品国产| 久久综合狠狠综合久久综合88 | 在线亚洲激情| 欧美一级片一区| 久久精品人人做人人爽| 久久亚洲国产精品日日av夜夜| 久久综合色88| 欧美日韩不卡一区| 国产精品青草久久久久福利99| 国产伦精品一区| 精品99一区二区| 亚洲日本成人| 亚洲一区二区毛片| 久久精品在线| 亚洲国产成人porn| 亚洲天堂久久| 久久久天天操| 欧美精品综合| 国产日韩一区欧美| 亚洲青涩在线| 亚洲永久在线观看| 久久香蕉国产线看观看网| 亚洲国产高清aⅴ视频| 99精品99| 久久久久久自在自线| 欧美日本在线看| 国产欧美日韩一区二区三区在线| 尤物网精品视频| 亚洲一区日本| 欧美第一黄网免费网站| 一本久久青青| 久久亚洲二区| 国产精品一区二区久久久| 亚洲第一精品夜夜躁人人爽| 亚洲网站在线观看| 女女同性精品视频| 亚洲视频精品| 欧美国产精品久久| 国产自产在线视频一区| 99热在线精品观看| 久久精品国产精品| 亚洲美女性视频| 久久精品国产视频| 国产精品国产三级国产专播精品人| 红桃视频国产精品| 午夜在线观看免费一区| 亚洲人成精品久久久久| 久久av二区| 国产精品主播| 一区二区三区国产在线| 欧美成人69av| 欧美在线视频a| 国产精品一区二区三区免费观看| 亚洲精品在线免费| 裸体歌舞表演一区二区| 午夜视频在线观看一区二区| 欧美日韩国产免费| 久久久久久久999| 欧美国产在线电影| 欧美a级大片| 亚洲欧美日本精品| 欧美午夜精品一区| 一区二区三区|亚洲午夜| 久久亚洲午夜电影| 美女脱光内衣内裤视频久久网站| 久久国产精彩视频| 欧美国产日韩一区二区| 一区二区欧美国产| 久久久久久自在自线| 欧美午夜视频| 亚洲韩国精品一区| 欧美在线观看你懂的| 欧美黑人在线播放| 午夜亚洲性色福利视频| 欧美人妖在线观看| 激情六月婷婷综合| 亚洲欧美成aⅴ人在线观看| 欧美成人黄色小视频| 亚洲一区二区三区久久 | 狂野欧美激情性xxxx| 日韩天堂av| 老司机一区二区三区| 国产欧美1区2区3区| 99精品黄色片免费大全| 美女网站久久| 午夜在线播放视频欧美| 欧美日韩一区二区三| 亚洲美女色禁图| 免费永久网站黄欧美| 欧美亚洲免费| 国产精品美女主播在线观看纯欲| 99日韩精品|