http://jsj.sdibt.edu.cn/judge/problem/viewProblem.action?id=329
题目大意:给出一个有向图。给出起点和终点,求出起点到终点的最短路径和次短路径的条数
输入:
第一行:测试数据的组数t
后面每组测试数据的第一行:顶点数n(2<=n<1000)边数m(1<=m<=10000)
每组测试数据随后的m行:每条边起点a和终点b,长度l
每组测试数据最后一行:起点s,终点f
输出:
每组测试数据输出一行:最短路径和次短路径的条数
解题思路:
1.采用邻接表存储整个有向图,数据结构如下;

typedef struct
{
	int v;//终点
	int weight;//边权值
}edge;//边

typedef struct
{
	edge edges[N][N];//每个顶点的边
	int degree[N];//每个顶点的度
	int nvertices;//顶点数
	int nedges;//边数
}graph;//图

2.开辟数组dist[N][2],dist[i][0]表示到i的最短路径长度,dist[i][1]表示到i的次短路径的长度。
3.开辟数组num[N][2],num[i][0]表示到i的最短路径数目,dist[i][1]表示到i的次短路径的数目。
4.根据一下四个规则进行更新:
    if(x<最小)更新最小,次小
    else if(x==最小)更新方法数
    else if(x<次小)更新次小
    else if(x==次小)更新方法数
5.最后num[f][0]即为所求
注意:因为有多组数据,所以要注意各个数组的初始化
核心代码:

void dijkstra()
{
	int i;
	bool isvis[N][2];
	int w;
	data tmp,tmp1;
	for(i=1;i<=g.nvertices;i++)
	{
		isvis[i][0]=false;
		isvis[i][1]=false;
		dist[i][0]=MAX;
		dist[i][1]=MAX;
		num[i][0]=0;
		num[i][1]=0;
	}
	priority_queue<data>que;
    dist[s][0]=0;
	tmp.id=s;
	tmp.flag=0;
	que.push(tmp);
	num[s][0]=1;
    while(!que.empty())
    {
        tmp=que.top();
		que.pop();
        if(isvis[tmp.id][tmp.flag]==true)
			continue;
        isvis[tmp.id][tmp.flag]=true;
        for(i=0;i<g.degree[tmp.id];i++)
        {
            w=dist[tmp.id][tmp.flag]+g.edges[tmp.id][i].weight;
            if(w<dist[g.edges[tmp.id][i].v][0])
            {
                if(dist[g.edges[tmp.id][i].v][0]!=MAX)
                {
                    dist[g.edges[tmp.id][i].v][1]=dist[g.edges[tmp.id][i].v][0];
                    num[g.edges[tmp.id][i].v][1]=num[g.edges[tmp.id][i].v][0];
					tmp1.id=g.edges[tmp.id][i].v;
					tmp1.flag=1;
					que.push(tmp1);
                }
                dist[g.edges[tmp.id][i].v][0]=w;
				num[g.edges[tmp.id][i].v][0]=num[tmp.id][tmp.flag];
                tmp1.id=g.edges[tmp.id][i].v;
				tmp1.flag=0;
				que.push(tmp1);
            }
            else if(w==dist[g.edges[tmp.id][i].v][0])
				num[g.edges[tmp.id][i].v][0]+=num[tmp.id][tmp.flag];
            else if(w<dist[g.edges[tmp.id][i].v][1])
            {
                dist[g.edges[tmp.id][i].v][1]=w;
				num[g.edges[tmp.id][i].v][1]=num[tmp.id][tmp.flag];
                tmp1.id=g.edges[tmp.id][i].v;
				tmp1.flag=1;
				que.push(tmp1);
            }
            else if(w==dist[g.edges[tmp.id][i].v][1])
				num[g.edges[tmp.id][i].v][1]+=num[tmp.id][tmp.flag];
        }
    }
    if(dist[f][1]-dist[f][0]==1)
		num[f][0]+=num[f][1];

发表评论

电子邮件地址不会被公开。

Post Navigation