单源最短路模板


 
一：SPFA
#define INF 1000000000  
#define MAXN 50010  //点个数  
#define MAXM 6000000 //边条数  
int dis[MAXN];//结果  
struct Node{  
    int v, next;  
    int  c;  
}E[MAXM];  
int head[MAXN];  
int NE;  
void init(int n)  
{  
    for (int i = 0; i <= n; i ++)  
    {  
        head[i] = -1;  
        dis[i] = INF;  
    }  
    NE = 0;   
}  
  
void insert(int x, int y, int c)  
{  
    E[NE].v = y;  
    E[NE].c = c;  
    E[NE].next = head[x];  
    head[x] = NE ++;  
}  
  
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;  
}  
 
二：dijstra
 
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.zzzyk.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;  
}

补充：综合编程 , 其他综合 ,