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

隨筆 - 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>
              久久精品99国产精品酒店日本| 午夜国产精品视频| 亚洲成人在线免费| 精品av久久707| 久久综合给合| 欧美日韩一区二区视频在线 | 国产精品中文字幕在线观看| 久久大逼视频| 欧美日韩国产一区精品一区 | 久久久久国产成人精品亚洲午夜| 亚洲国产小视频| 午夜视频一区在线观看| 91久久精品日日躁夜夜躁欧美| 亚洲视频在线播放| 亚洲精品永久免费| 久久亚洲国产精品一区二区 | 亚洲小视频在线| 日韩亚洲精品电影| 模特精品裸拍一区| 久久久综合网站| 亚洲激情黄色| 亚洲一区区二区| 欧美色大人视频| 亚洲国产精品va在线看黑人动漫| 国产精品爽黄69| 亚洲欧美日本国产有色| 99精品久久久| 欧美日韩一区二区视频在线| 亚洲人成人一区二区三区| 亚洲激情电影在线| 欧美精品啪啪| 亚洲少妇诱惑| 欧美一二区视频| 国产精品视频第一区| 亚洲天堂免费观看| 久久永久免费| 日韩视频三区| 国产精品久久久久久久第一福利 | 久久嫩草精品久久久久| 女女同性女同一区二区三区91| 亚洲国产va精品久久久不卡综合| 久久青草欧美一区二区三区| 99re6热在线精品视频播放速度| 亚洲小说欧美另类社区| 好吊日精品视频| 欧美日韩成人一区二区| 亚洲免费影视| 亚洲人成网站影音先锋播放| 久久www成人_看片免费不卡| 亚洲成人原创| 国产一区二区无遮挡| 欧美区一区二区三区| 久久免费国产精品| 亚洲免费在线精品一区| 99视频精品全国免费| 欧美激情小视频| 久久久久久久久久久久久9999| 亚洲黄色成人网| 亚洲激情六月丁香| 激情综合色综合久久| 国产麻豆日韩欧美久久| 国产精品成人播放| 欧美日韩亚洲在线| 欧美人成在线视频| 欧美日韩日韩| 国产精品久久久久久户外露出| 欧美精选一区| 欧美日韩一二区| 欧美三级午夜理伦三级中文幕| 欧美精品一区三区| 欧美激情第8页| 欧美三级视频| 国产免费观看久久黄| 国产女精品视频网站免费| 国产精品一二一区| 国产色产综合色产在线视频| 国内精品美女在线观看| 国产综合18久久久久久| 亚洲国产精品第一区二区三区| 亚洲大胆女人| 亚洲欧美日韩国产精品| 久久成人资源| 亚洲国产视频a| 久久午夜视频| 久久久久久久综合狠狠综合| 老牛嫩草一区二区三区日本| 亚洲国产精品激情在线观看| 亚洲图片欧美午夜| 久久久www成人免费无遮挡大片| 欧美99久久| 国产综合久久久久久鬼色| 夜夜嗨av色一区二区不卡| 欧美一区二区三区免费视频| 美女视频一区免费观看| 宅男在线国产精品| 亚洲人成小说网站色在线| 亚洲精选在线| 久久精品系列| 亚洲伦理在线观看| 欧美精品成人| 亚洲国产精品免费| 欧美不卡高清| 欧美专区中文字幕| 国产精品久在线观看| 亚洲最新视频在线| 欧美二区在线| 久久精品观看| 亚洲精品中文字幕在线| 欧美高清你懂得| 欧美日韩的一区二区| 一本大道久久a久久精二百| 亚洲精品在线视频观看| 欧美日韩日本国产亚洲在线| 午夜国产精品视频| 欧美在线资源| 亚洲黄一区二区三区| 日韩视频精品| 国产一区二区三区在线观看网站| 久久视频免费观看| 欧美精品一区二区三区视频| 性欧美办公室18xxxxhd| 男男成人高潮片免费网站| 午夜精品亚洲| 欧美激情精品久久久六区热门| 亚洲欧美成人在线| 欧美精品一区二区在线播放| 久久国产精品亚洲77777| 欧美三级日本三级少妇99| 久久视频一区二区| 国产欧美午夜| 亚洲综合国产精品| 中日韩美女免费视频网站在线观看| 欧美一级久久| 久久精彩视频| 国产性猛交xxxx免费看久久| 亚洲视频 欧洲视频| 中文日韩电影网站| 欧美日韩国产一区二区三区地区| 久久野战av| 亚洲国产精品成人精品| 欧美成黄导航| 99精品视频免费全部在线| 亚洲日本理论电影| 欧美日韩色婷婷| 久久精品91久久久久久再现| 久久久精品国产免费观看同学| 欧美午夜精品理论片a级按摩| 亚洲人成网站精品片在线观看| 99精品视频一区二区三区| 欧美日韩免费观看一区| 亚洲综合电影| 牛牛国产精品| 亚洲午夜精品网| 国产亚洲成精品久久| 快射av在线播放一区| 一区二区三区日韩在线观看| 欧美亚洲综合在线| 亚洲国产小视频在线观看| 欧美日韩www| 久久成人一区二区| 日韩视频永久免费| 欧美刺激性大交免费视频| 亚洲欧美一区二区三区极速播放| 国产一区二区三区直播精品电影| 免费看的黄色欧美网站| 亚洲女人小视频在线观看| 亚洲电影在线| 麻豆成人综合网| 国产精品99久久久久久久久| 91久久线看在观草草青青| 国产精品视频第一区| 欧美视频一区二区| 免费看成人av| 欧美freesex8一10精品| 久久久一二三| 老司机精品视频网站| 久久九九电影| 久久久久久黄| 久久在线视频在线| 亚洲大片av| 欧美顶级少妇做爰| 亚洲第一在线| 99视频精品全部免费在线| 亚洲人成在线观看一区二区| 亚洲大胆美女视频| 亚洲黄一区二区| 亚洲精品社区| 一区二区毛片| 亚洲先锋成人| 久久米奇亚洲| 美女诱惑一区| 亚洲成色www8888| 亚洲精品精选| 亚洲一区二区三区影院| 在线性视频日韩欧美| 午夜久久99| 欧美亚洲成人免费| 亚洲精品日韩在线观看| 欧美一区精品| 亚洲日本一区二区|