首页 > > 程序设计 > C/C++ >

codevs 1021 玛丽卡（spfa）

2018-06-17 23:47:41来源：未知阅读 ()

题目描述 Description

麦克找了个新女朋友，玛丽卡对他非常恼火并伺机报复。

因为她和他们不住在同一个城市，因此她开始准备她的长途旅行。

在这个国家中每两个城市之间最多只有一条路相通，并且我们知道从一个城市到另一个城市路上所需花费的时间。

麦克在车中无意中听到有一条路正在维修，并且那儿正堵车，但没听清楚到底是哪一条路。无论哪一条路正在维修，从玛丽卡所在的城市都能到达麦克所在的城市。

玛丽卡将只从不堵车的路上通过，并且她将按最短路线行车。麦克希望知道在最糟糕的情况下玛丽卡到达他所在的城市需要多长时间，这样他就能保证他的女朋友离开该城市足够远。

编写程序，帮助麦克找出玛丽卡按最短路线通过不堵车道路到达他所在城市所需的最长时间(用分钟表示)。

输入描述 Input Description

第一行有两个用空格隔开的数N和M，分别表示城市的数量以及城市间道路的数量。1≤N≤1000，1≤M≤N*(N-1)/2。城市用数字1至N标识，麦克在城市1中，玛丽卡在城市N中。

接下来的M行中每行包含三个用空格隔开的数A，B和V。其中1≤A，B≤N，1≤V≤1000。这些数字表示在A和城市B中间有一条双行道，并且在V分钟内是就能通过。

输出描述 Output Description

输出文件的第一行中写出用分钟表示的最长时间，在这段时间中，无论哪条路在堵车，玛丽卡应该能够到达麦克处，如果少于这个时间的话，则必定存在一条路，该条路一旦堵车，玛丽卡就不能够赶到麦克处。

样例输入 Sample Input

5 7

1 2 8

1 4 10

2 3 9

2 4 10

2 5 1

3 4 7

3 5 10

样例输出 Sample Output

这道题用spfa解的话我们先跑一遍spfa来求出最短路。在此过程中呢，我们要记录每一个点的最短路是由哪一个点走过来的（意思是没将一个点的最短距离更新，那么便将这个点的最短路来源换成当前点）。

接下来我们从点n开始往回找点

for(i=n;i!=1;i=p[i])//p[i]记录的是i这个点的最短路是从哪个点走过来的
  q[++c]=i;
q[++c]=1;//q数组记录的是最短路上的所有点

这段代码记录了最短路上所有点

接着我们进行枚举，枚举所有最短路上的每一条路堵车时的1——n的最短路

接着求出这些路中花费时间最长的路（因为我们考虑的是最短路的最差值）

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
 int next,z,v;
}b[1100000];
int n,m,l[1010],d[100000],h,t,i,j,e,p[10000],q[1001],cnt,c,x,y,w,hh[2000],u,vv,ans;
bool dd[100000];
void add(int aa,int bb,int cc)
{
 b[++cnt].v=bb;
 b[cnt].next=hh[aa];
 b[cnt].z=cc;
 hh[aa]=cnt;    
}
int main()
{
 scanf("%d %d",&n,&m);
 for(i=1;i<=m;i++)
 {
  scanf("%d %d %d",&x,&y,&w);
  add(x,y,w);add(y,x,w);//邻接表用来存边
 }
 
 memset(l,0x3f,sizeof(l));//将每一条路的最短距离赋为最大值
 l[1]=0;//起始点为点1，所以到点1的最短距离是0
 x=1;
 while(1)
 {
  if(h>t)break;
  j=hh[x];
  while(1)
  {
   e=b[j].v;
   if(l[x]+b[j].z<l[e]){
       l[e]=l[x]+b[j].z;
       p[e]=x;
       if(dd[e]==false)dd[e]=true,d[++t]=e;//dd数组记录的是当前点是否在队列中，如果不在就将其入队；
   }
   if(b[j].next==0)break;
   j=b[j].next;
  }
  dd[x]=false;
  x=d[++h];
  
 }
 for(i=n;i!=1;i=p[i])
  q[++c]=i;
 ans=0;
 q[++c]=1;

 while(1)
 {
  memset(l,0x3f,sizeof(l));
  l[1]=0;
  u=q[i];
  vv=q[++i];//u,vv记录的是要堵车的路的两个点
  h=0;t=0;
  x=1;
  while(1)
  {
    if(h>t)break;
    j=hh[x];
   while(1)
   {
      e=b[j].v;
      if((u==x&&vv==e)||(vv==x&&u==e))
      {    
             if(b[j].next==0)break;
             j=b[j].next;
             continue;
      }
      if(l[x]+b[j].z<l[e]){
          l[e]=l[x]+b[j].z;
          p[e]=x;
       if(dd[e]==false)dd[e]=true,d[++t]=e;
     }
    if(b[j].next==0)break;
    j=b[j].next;
  }
  dd[x]=false;
  x=d[++h];
 }
  ans=max(ans,l[n]);
  if(i==c)break;   //当所有最短路上的边都枚举过了就打断 
 }
 printf("%d",ans);
return 0;
}