【HDU、最短路/3大模板】总结_C/C++_编程开发_程序员俱乐部

#define inf 0x3fffffff
#define M 105

int dist[M], map[M][M], n;
bool mark[M];

void init ()
{
	int i, j;
	for (i = 1; i <= n; i++)    //i==j的时候也可以初始化为0，只是有时候不合适
		for (j = 1; j <= n; j++)
			map[i][j] = inf;
}

void dijk (int u)
{
	int i, j, mins, v;
	for (i = 1; i <= n; i++)
	{
		dist[i] = map[u][i];
		mark[i] = false;
	}
	mark[u] = true;
	dist[u] = 0;    //既然上面的map当i==j时不是0，就要这句
	while (1)
	{
		mins = inf;
		for (j = 1; j <= n; j++)
			if (!mark[j] && dist[j] < mins)
				mins = dist[j], v = j;
		if (mins == inf)
			break;
		mark[v] = true;
		for (j = 1; j <= n; j++)
			if (!mark[j] && dist[v] + map[v][j] < dist[j])
				dist[j] = dist[v] + map[v][j];
	}
}

#define inf 0x3fffffff	//注意，太大会溢出
#define M				//最大点数
int n, dist[M][M];           //n：实际点数

void init ()			//有时候需要初始化
{
    int i, j;
    for (i = 1; i <= n; i++)
        for (j = i + 1; j <= n; j++)
            dist[i][j] = dist[j][i] = inf;
}

void floyd ()
{
    int i, j, k;
    for (k = 1; k <= n; k++)
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++)    //有的题目会溢出就要自己变通了
                if (dist[i][k] + dist[k][j] < dist[i][j])
	                    dist[i][j] = dist[i][k] + dist[k][j];
}

#define inf 0x3fffffff
#define M 105    //最大点数
struct son{
    int v, w;
};
vector<son> g[M];
bool inq[M];       //入队列标记
int dist[M], n;    //n：实际点数

void init ()
{
	for (int i = 1; i <= n; i++)
		g[i].clear();
}

void spfa (int u)
{
    int i, v, w;
    for (i = 1; i <= n; i++)
    {
        dist[i] = inf;
        inq[i] = false;
    }
    queue<int> q;
    q.push (u);
    inq[u] = true;
    dist[u] = 0;
    while (!q.empty())
    {
        u = q.front();
        q.pop();
        inq[u] = false;
        for (i = 0; i < g[u].size(); i++)
        {
            v = g[u][i].v;
            w = g[u][i].w;
            if (dist[u] + w < dist[v])
            {
                dist[v] = dist[u] + w;
                if (!inq[v])
                {
                    q.push (v);
                    inq[v] = true;
                }
            }
        }
    }
}