Bellman-Ford算法

buaa通向女友之路~水~模板

WARush posted @ 2010年10月12日 02:01 in ACM杂题不解释 with tags dijkstra ACM , 1290 阅读

 

吉大模板A的水,不知道ab同学怎么能tle的。。。。dijkstra
#include <cstdlib>
#include <limits>
#include <ctime>
#include <memory>
#include <cmath>
#include <functional>
#include <numeric>
 
#include <cstdio>
#include <iostream>
#include <fstream>
//#include <strstream>
 
#include <algorithm>
#include <iterator>
#include <map>
#include <set>
//#include <ext/hash_map>
//#include <ext/hash_set>
//#include <hash_map>
//#include <hash_set>
#include <queue>
#include <stack>
#include <list>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
 
using namespace std;
 
/*==================================================*\
| Dijkstra O(E * log E)
| INIT: 调用init(nv, ne)读入边并初始化;
| CALL: dijkstra(n, src); dist[i]为src到i的最短距离
\*==================================================*/
#define typec int // type of cost
#define V 10001
#define E 100001
const typec inf = 0x3f3f3f3f; // max of cost
typec cost[E], dist[V];
int e, pnt[E], nxt[E], head[V], prev[V], vis[V];
 
struct qnode {
    int v;
    typec c;
 
    qnode(int vv = 0, typec cc = 0) : v(vv), c(cc) {
    }
 
    bool operator<(const qnode & r) const {
        return c > r.c;
    }
};
 
void dijkstra(int n, const int src) {
    qnode mv;
    int i, j, k, pre;
    priority_queue<qnode> que;
    vis[src] = 1;
    dist[src] = 0;
    que.push(qnode(src, 0));
    for (pre = src, i = 1; i < n; i++) {
        for (j = head[pre]; j != -1; j = nxt[j]) {
            k = pnt[j];
            if (vis[k] == 0 &&
                    dist[pre] + cost[j] < dist[k]) {
                dist[k] = dist[pre] + cost[j];
                que.push(qnode(pnt[j], dist[k]));
                prev[k] = pre;
            }
        }
        while (!que.empty() && vis[que.top().v] == 1)
            que.pop();
        if (que.empty()) break;
        mv = que.top();
        que.pop();
        vis[pre = mv.v] = 1;
    }
}
 
inline void addedge(int u, int v, typec c) {
    pnt[e] = v;
    cost[e] = c;
    nxt[e] = head[u];
    head[u] = e++;
}
 
void init(int nv, int ne) {
    int i, u, v;
    typec c;
    e = 0;
    memset(head, -1, sizeof (head));
    memset(vis, 0, sizeof (vis));
    memset(prev, -1, sizeof (prev));
    for (i = 0; i < nv; i++) dist[i] = inf;
    for (i = 0; i < ne; ++i) {
        scanf("%d%d%d", &u, &v, &c); // %d: type of cost
        //printf("%d%d%d\n", u, v, c);
        u--;
        v--;
        addedge(u, v, c); // vertex: 0 ~ n-1, 单向边
        //addedge(v, u, c);
    }
}
 
int main() {
    int m, n;
    int s,t;
    while(cin >> n >> m) {
        init(n, m);
        //printf("%d", e);
        cin>>s>>t;
        dijkstra(n, s-1);
        cout << dist[t-1] << endl;
    }
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter