学步园

Dijkstra。

#include <stdio.h>
#include <string.h>

#define CLR(a,v) memset(a,v,sizeof(a))
#define min(a,b) a < b ? a : b

#define N 105
#define M 10005

struct Vertex
{
	int head;
}V[N];

struct Edge
{
	int v,w,next;
}E[M];

int n,m,top,d[N];

bool in[N];

void Init()
{
	CLR(in,false);
	CLR(d,63);
	CLR(V,-1);
	top = 0;
}

void Add_Edge(int u,int v,int w)
{
	E[top].v = v;
	E[top].w = w;
	E[top].next = V[u].head;
	V[u].head = top++;
}

void Dijkstra(int s)
{
	int p = s,t = n;
	d[s] = 0;
	do
	{
	    in[p] = true;
		for(int i=V[p].head;i!=-1;i=E[i].next)
		{
			int q = E[i].v;
			if(!in[q])
                d[q] = min(d[q],d[p]+E[i].w);
		}
		int mmin = d[0];
		for(int i=1;i<=n;i++)
			if(!in[i] && d[i] < mmin)
				mmin = d[i] , p = i;
	}while(--t > 1);
}

Dijkstra + 优先队列。

#include <queue>
#include <stdio.h>
#include <string.h>

using namespace std;

#define CLR(a,v) memset(a,v,sizeof(a))
#define min(a,b) a < b ? a : b

#define N 105
#define M 10005

struct Vertex
{
	int head;
}V[N];

struct Edge
{
	int v,w,next;
}E[M];

struct Node
{
    Node(int u,int w):u(u),w(w){}
    int u,w;
    bool operator < (const Node& S)const
	{
	    return w > S.w;
	}
};

int n,m,top,d[N];

bool in[N];

void Init()
{
    CLR(in,false);
	CLR(d,63);
	CLR(V,-1);
	top = 0;
}

void Add_Edge(int u,int v,int w)
{
	E[top].v = v;
	E[top].w = w;
	E[top].next = V[u].head;
	V[u].head = top++;
}

void Dijkstra(int s)
{
	int p = s,t = n;
	d[s] = 0;
	priority_queue<Node> Q;
	Q.push(Node(s,0));
	while(!Q.empty())
	{
	    Node R = Q.top();Q.pop();
	    int p = R.u;
	    if(in[p])
            continue;
	    in[p] = true;
		for(int i=V[p].head;i!=-1;i=E[i].next)
		{
			int q = E[i].v;
			if(!in[q] && d[p]+E[i].w < d[q])
			{
			    d[q] = d[p]+E[i].w;
			    Q.push(Node(q,d[q]));
			}
		}
	}
}

Spfa。

#include <queue>
#include <stdio.h>
#include <string.h>

using namespace std;

#define CLR(a,v) memset(a,v,sizeof(a))
#define min(a,b) a < b ? a : b

#define N 105
#define M 10005

struct Vertex
{
	int head;
}V[N];

struct Edge
{
	int v,w,next;
}E[M];

int n,m,top,d[N];

bool in[N];

void Init()
{
    CLR(in,false);
	CLR(d,63);
	CLR(V,-1);
	top = 0;
}

void Add_Edge(int u,int v,int w)
{
	E[top].v = v;
	E[top].w = w;
	E[top].next = V[u].head;
	V[u].head = top++;
}

void Spfa(int s)
{
    queue<int> Q;
    Q.push(s);
    d[s] = 0;
    in[s] = true;
	while(!Q.empty())
	{
	    int p = Q.front();
		for(int i=V[p].head;i!=-1;i=E[i].next)
		{
			int q = E[i].v;
			if(d[p]+E[i].w < d[q])
			{
			    d[q] = d[p]+E[i].w;
			    if(!in[q])
                    Q.push(q);
                in[q] = true;
			}
		}
		Q.pop();
		in[p] = false;
	}
}

Floyd。

void Floyd()
{
    CLR(d,63);
    for(int i=1;i<=n;i++)
        d[i][i] = 0;
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
}