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 ≤ X ≤ N). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires T_i (1 ≤ T_i ≤ 100) units of time to traverse.

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: A_i, B_i, and T_i. The described road runs from farm A_i to farm B_i, requiring T_i 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参数均为外部编号,wt为其权值
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 == -1) return 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;
}