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

2010年10月12日 02:01

 

吉大模板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;
}

Posted by WARush Filed in ACM杂题不解释 Tagged by dijkstra 水 ACM Comments[4]

Bellman-Ford算法

2010年7月21日 04:12

#include<iostream>
using namespace std;
const int V=101;
const int E=101;
#define typec int                      // type of cost
const typec inf=0x3f3f3f3f;            // max of cost
int n, m, pre[V], edge[E][3];
typec dist[V];
int relax (int u, int v, typec c)
{
    if (dist[v] > dist[u] + c)
    {
        dist[v] = dist[u] + c;
        pre[v] = u;
        return 1;
    }
    return 0;
}
int bellman (int src)
{
    int i, j;
    for (i=0; i<n; ++i)
    {
        dist[i] = inf;
        pre[i] = -1;
    }
    dist[src] = 0;
    bool flag;
    for (i=1; i<n; ++i)
    {
        flag = false; 
        for (j=0; j<m; ++j)
        {
            if( 1 == relax(edge[j][0], edge[j][1],
                           edge[j][2])  ) flag = true;
        }
        if( !flag ) break;
    }
    for (j=0; j<m; ++j)
    {
        if (1 == relax(edge[j][0], edge[j][1], edge[j][2]))
            return 0
    }
    return 1;
}

int main()
{
    int i;
    int src;
    cin>>n>>m;

    for(i=0; i<m; ++i)
    {
        cin>>edge[i][0]>>edge[i][1]>>edge[i][2];
        
    }

  
    cin>>src;
    cout<<bellman(src)<<"\n";
    for(i=0; i<n; i++)
    {
        cout<<dist[i]<<' ';
    }
    cout<<'\n';
    return 0;
}

模版的使用，Bellman-Ford算法，复杂度O(VE)，可解决负权边，判别负权回路。

额外采用Yen氏改进，但不降低渐进复杂度。还可采用队列优化成SPFA(Shortest Path Faster Algorithm)。

 

Posted by WARush Filed in ACM杂题不解释 Tagged by Bellman-Ford 负权边 负权回路 Yen氏改进 ACM Comments[21]