POJ 1847 最短路径垃圾水题可是坑爹多case问题初始化的锅

Tram

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 13527		Accepted: 4978

Description

Tram network in Zagreb consists of a number of intersections and rails connecting some of them. In every intersection there is a switch pointing to the one of the rails going out of the intersection. When the tram enters the intersection it can leave only in the direction the switch is pointing. If the driver wants to go some other way, he/she has to manually change the switch.

When a driver has do drive from intersection A to the intersection B he/she tries to choose the route that will minimize the number of times he/she will have to change the switches manually.

Write a program that will calculate the minimal number of switch changes necessary to travel from intersection A to intersection B.

Input

The first line of the input contains integers N, A and B, separated by a single blank character, 2 <= N <= 100, 1 <= A, B <= N, N is the number of intersections in the network, and intersections are numbered from 1 to N.

Each of the following N lines contain a sequence of integers separated by a single blank character. First number in the i-th line, Ki (0 <= Ki <= N-1), represents the number of rails going out of the i-th intersection. Next Ki numbers represents the intersections directly connected to the i-th intersection.Switch in the i-th intersection is initially pointing in the direction of the first intersection listed.

Output

The first and only line of the output should contain the target minimal number. If there is no route from A to B the line should contain the integer "-1".

Sample Input

Sample Output

题意不好理解，读懂了就简单了，有向图，第一行依次是N个点，起始点，目的点，剩下跟着N行，每行第一个是第k点的连通数，比如2 2 3，代表第一个点 1-2=0,1-3=1，除了第一个点的权值是0，后面的边的权值都是1.

坑啊，搞了一天终于明白了，Dj的这个模板是书上一个数据的模板的，如果多个数据，第一个case =1，那第一次展开后if没进去，则u为0，输出结果dis[start]=0，而第二轮后没被初始化的全局变量随机，e[0][v]为负值的话，就GG了。

1.去掉book[start]=1的展开，这样即是第一个case为1，也进得去if的找最小边，u=1，而在下面的松弛中，只有dis[start]=0

2.在dis[j]<minn加等于号（目前不知道为什么）

3.判断u==0的情况，如下面代码，如果没有筛选到最近的边，u还是0，直接break。

4.u直接等于1，这样就去掉了e[0][]的负值情况。

总结：还是要多注意多个case下的初始化问题啊

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 99999999;
const int maxn = 220;

int e[maxn][maxn],dis[maxn],i,j,book[maxn],minn,tmp;
int u,v;
int n,start,eend,m,t1,t2,t3;




int main()
{
//   freopen("in.txt","r",stdin);
   while(scanf("%d %d %d",&n,&start,&eend)!=EOF){

   for(i=1;i<=n;i++){
            dis[i]=INF;
        for(j=1;j<=n;j++)
        if(i==j)
         e[i][j]=0;
         else
            e[i][j]=INF;
}

   for(i=1;i<=n;i++){
     scanf("%d",&m);

      for(j=1;j<=m;j++){
        scanf("%d",&t1);
        if(j==1)
            e[i][t1]=0;
            else
            e[i][t1]=1;
      }
    }


 for(i=1;i<=n;i++)
    dis[i]=e[start][i];
    dis[start]=0;//如果start和eend都是自己

 memset(book,0,sizeof(book));
 book[start]=1;



 for(i=1;i<=n-1;i++){
    minn=INF;
    u=0;
    for(j=1;j<=n;j++){
        if(book[j]==0&&dis[j]<minn){
            minn=dis[j];
            u = j;
        }
    }
    if(u==0||u==eend){ //只要没筛选上次n=1的问题或者要找出边的点已经是eend点了
        break;
    }   
    book[u]=1;
    for(v=1;v<=n;v++){
        if(e[u][v]<INF){
            if(dis[v]>dis[u]+e[u][v])
                dis[v]=dis[u]+e[u][v];
        }
    }
 }

   if(dis[eend]<INF)
      printf("%d
",dis[eend]);
   else
       cout<<"-1"<<endl;
   }
 return 0;
}

Folyd一次就过了，没有那个情况的考虑了

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 99999999;
const int maxn = 105;

int e[maxn][maxn],dis[maxn],i,j,book[maxn],minn,tmp;
int u,v;
int n,start,eend,m,t1,t2,t3;

void init(){
     for(i=1;i<=n;i++){
            dis[i]=INF;
        for(j=1;j<=n;j++)
        if(i==j)
         e[i][j]=0;
         else
            e[i][j]=INF;
}
}
int main()
{
   //freopen("in.txt","r",stdin);
   while(scanf("%d %d %d",&n,&start,&eend)!=EOF){;
   init();

   for(i=1;i<=n;i++){
     scanf("%d",&m);

      for(j=1;j<=m;j++){
        scanf("%d",&t1);
        if(j==1)
            e[i][t1]=0;
            else
            e[i][t1]=1;
      }
    }


 for(int k = 1;k<=n;k++)
    for(i=1;i<=n;i++)
       for(j=1;j<=n;j++)
        if(e[i][j]>e[i][k]+e[k][j])
           e[i][j]=e[i][k]+e[k][j];

   if(e[start][eend]<INF)
      printf("%d
",e[start][eend]);
   else
       cout<<"-1"<<endl;
   }
 return 0;
}

POJ 1847 最短路径 垃圾水题可是坑爹多case问题初始化的锅

POJ 1847 最短路径垃圾水题可是坑爹多case问题初始化的锅