路由选择(codevs 1062)

题目描述 Description

在网络通信中,经常需要求最短路径。但完全用最短路径传输有这样一个问题:如果最终在两个终端节点之间给出的最短路径只有一条。则在该路径中的任一个节点或链路出现故障时,信号传输将面临中断的危险。因此,对网络路由选择作了以下改进:

为任意两节点之间通信提供三条路径供其选择,即最短路径、第二最短路径和第三最短路径。

第一最短路径定义为:给定一个不含负回路的网络D={V,A,W},其中V={v1,v2,…,vn},A为边的集合,W为权的集合,设P1是D中最短(v1,vn)路。称P1为D中最短(v1,vn)路径,如果D中有一条(v1,vn)路,P2满足以下条件:

(1)P2≠P1;(2)D中不存在异于P1的路P,使得:

(3)W(P1)≤W(P)<W(P2)

则称P2为D的第二最短路径。

第三最短路径的定义为:设P2是D中第二最短(v1,vn)路径,如果D中有一条(v1,vn)路P3满足以下条件:

(1)P3≠P2并且P3≠P1;(2)D中不存在异于P1,P2的路P,使得:

(3)W(P2)≤W(P)<W(P3)

则称P3为D中第三最短路径。

现给定一有N个节点的网络,N≤30,求给定两点间的第一、第二和第三最短路径。

输入描述 Input Description

输入:  n  S  T  Max   (每格数值之间用空格分隔)

M11  M12  …  M1n

M21  M22  …  M2n

…   …

Mn1  Mn2  …  Mnn

其中,n为节点数,S为起点,T为终点,Max为一代表无穷大的整数,Mij描述I到J的距离,若Mij=Max,则表示从I到J无直接通路,Mii=0。

输出描述 Output Description

输出:三条路径(从小到大输出),每条路径占一行,形式为:路径长度 始点…终点  (中间用一个空格分隔)

样例输入 Sample Input

5  1       5     10000

0         1         3         10000     7

10000     0          1         10000     10000

10000     10000     0         1         4

10000     10000     10000     0        1

10000     1         10000     10000     0

样例输出 Sample Output

4  1  2  3  4  5

5  1  3  4  5

6  1  2  3  5

/*
用Dij搞了半天,没搞出来,然而数据太水,DFS可过
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 35
#define M 300100
using namespace std;
int map[N][N],vis[N],b[N],n,s,t,maxn,cnt;
struct node
{
int dis,tot,step[N];
};node a[M];
void init(int p,int dis)
{
a[++cnt].tot=p-;
a[cnt].dis=dis;
for(int i=;i<p;i++)
a[cnt].step[i]=b[i];
}
void dfs(int x,int p,int dis)
{
if(p==&&x==)
int aa=;
if(x==t)
{
init(p,dis);
return;
}
vis[x]=;
for(int i=;i<=n;i++)
if(!vis[i]&&map[x][i])
{
b[p]=i;
vis[i]=;
dfs(i,p+,dis+map[x][i]);
vis[i]=;
}
}
bool cmp(const node&x,const node&y)
{
if(x.dis<y.dis)return true;
return false;
}
int main()
{
scanf("%d%d%d%d",&n,&s,&t,&maxn);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
scanf("%d",&map[i][j]);
if(map[i][j]==maxn)map[i][j]=;
}
dfs(s,,);
sort(a,a+cnt+,cmp);
printf("%d %d ",a[].dis,s);
for(int i=;i<=a[].tot;i++)
printf("%d ",a[].step[i]);printf("\n");
printf("%d %d ",a[].dis,s);
for(int i=;i<=a[].tot;i++)
printf("%d ",a[].step[i]);printf("\n");
printf("%d %d ",a[].dis,s);
for(int i=;i<=a[].tot;i++)
printf("%d ",a[].step[i]);printf("\n");
}
上一篇:Codeforces 396A 数论,组合数学


下一篇:codevs 1052 地鼠游戏