路由选择（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-1;
    a[cnt].dis=dis;
    for(int i=0;i<p;i++)
      a[cnt].step[i]=b[i];
}
void dfs(int x,int p,int dis)
{
    if(p==1&&x==4)
      int aa=1;
    if(x==t)
    {
        init(p,dis);
        return;
    }
    vis[x]=1;
    for(int i=1;i<=n;i++)
      if(!vis[i]&&map[x][i])
      {
          b[p]=i;
          vis[i]=1;
          dfs(i,p+1,dis+map[x][i]);
          vis[i]=0;
      }
}
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=1;i<=n;i++)
      for(int j=1;j<=n;j++)
      {
          scanf("%d",&map[i][j]);
          if(map[i][j]==maxn)map[i][j]=0;
      }
    dfs(s,0,0);
    sort(a,a+cnt+1,cmp);
    printf("%d %d ",a[1].dis,s);
      for(int i=0;i<=a[1].tot;i++)
        printf("%d ",a[1].step[i]);printf("
");
    printf("%d %d ",a[2].dis,s);
      for(int i=0;i<=a[2].tot;i++)
        printf("%d ",a[2].step[i]);printf("
");
    printf("%d %d ",a[3].dis,s);
      for(int i=0;i<=a[3].tot;i++)
        printf("%d ",a[3].step[i]);printf("
");
}

View Code