2013-02-02 10:29:20

#define INF 1000000000

#define MAXN 50010  //点个数

#define MAXM 6000000 //边条数

int dis[MAXN];//结果

struct Node{

int v, next;

int  c;

}E[MAXM];

int NE;

void init(int n)

{

for (int i = 0; i <= n; i ++)

{

dis[i] = INF;

}

NE = 0;

}

void insert(int x, int y, int c)

{

E[NE].v = y;

E[NE].c = c;

}

bool spfa(int s, int n)//s为起点

{

int p,i;

queue<int>q;

while(!q.empty())

q.pop();

bool hash[MAXN];

int count[MAXN];

memset (count, 0, sizeof(int) * (n + 2));

memset(hash,0,sizeof(bool) * ( n + 2)) ;

hash[s] = 1;

dis[s] = 0;

q.push(s);

count [s] = 1;

while(!q.empty())

{

p = q.front();

q.pop();

if(count[p] > n)

return false; //负环

hash[p] = 0;

for(i = head[p]; i != -1; i = E[i].next)

{

int v = E[i].v;

int cc = E[i].c;

if(dis[p] + cc < dis[v] || dis[v] == INF)

//v - u <= k时候是这样的,如果v - u >= k 改符号

{

dis[v] = dis[p] + cc;

if(hash[v] == 0)

{

count[v] ++;

hash[v] = 1;

q.push(v);

}

}

}

}

return 1;

}

const int N = 1001; //点

using namespace std;

struct node

{

int l,dir;

}w;//边

struct In

{

int idx;

int l;

bool friend operator<(const In &a, const In &b)

{

return a.l > b.l;

}

}ww,zz;//bfs

vector<node>mmap[N];

priority_queue<In>q;

int dis[N];

int start, end; //start 起点, end 终点

int nodenum;//点数 = end

int n, m;

int base;

void init()

{

while (!q.empty())

q.pop();

int i;

for (i = 0; i <= nodenum; i++)

{

dis[i] = -1;

mmap[i].clear();

}

return;

}

inline void creat(int s, int e, int value)

{

w.l = value;

w.dir = e;

mmap[s].push_back(w);

return;

}

void dij()

{

int i, j;

ww.idx = start;

ww.l = 0;

int size = 0;

node now;

q.push(ww);

while (!q.empty())

{

ww = q.top();

q.pop();

if (dis[ww.idx] != -1)

continue;

dis[ww.idx] = ww.l;

if(ww.idx == end)

return;  www.2cto.com

size = mmap[ww.idx].size();

for (i = 0;i < size; i++)

{

now = mmap[ww.idx][i];

zz.idx = now.dir;

zz.l = ww.l + now.l;

if(dis[zz.idx] == -1)

{

q.push(zz);

}

}

}

return;

}