[Wikioi 1021]玛丽卡(疑偏题)

[Wikioi 1021]玛丽卡(疑难题)

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

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

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

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

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

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

第一行有两个用空格隔开的数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分钟内是就能通过。

 

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

5 7

1 2 8

1 4 10

2 3 9

2 4 10

2 5 1

3 4 7

3 5 10

27

 

题目思路：

上图是样例数据的模拟图。

此题是一道裸SPFA问题，题目意思就是求删去一条边后的无向图单源最短路最大值。
首先跑一遍SPFA，记录下最短路径，然后一次次枚举删除最短路径中的一条边，跑spfa，判断当前最短路径是否大于最大最短路，更新最大最短路，然后输出最大最短路即可。

这里的SPFA过程可以只写一个函数，用变量flag来记录是否是第一次SPFA，如果是第一次的话，每次扩展一个点，就用数组记录下路径。

最后注意下开数组的问题，这题数据量暴大，要开大点数组，否则最后一个点永远RE

//题目大意：求删去一条边后的无向图单源最短路最大值
//注意SPFA方向是从终点n到起点1(玛丽卡在点N)
#include <stdio.h>
#include <queue>
#define MAXN 2000000
#define INF 10000000
using namespace std;
int n,m,start;
int u[MAXN],v[MAXN],f[MAXN],fu[MAXN]; //u[i]=边i的起点，v[i]=边i的终点，f[i]=结点i为起点的有向边的编号,fu数组保存最短路径
bool flag=1,del[MAXN],visit[MAXN]; //flag=1表示正在跑第一次SPFA,以后的SPFA不用记录最短路径；del[i]=第i条边被删除了,visit数组保存结点是否访问过
int next[MAXN],d[MAXN]; //next[i]=第i个结点对应的边,d[i]=第i条边对应的权值
int dist[MAXN]; //dist[i]=到达i点的最短路距离
void SPFA()
{
 int i,j;
 queue<int>q;
 for(i=1;i<=n;i++) dist[i]=INF;
 dist[start]=0; //初始化到达起点的最短路为0
 visit[start]=1; //标记起点访问过
 q.push(start);
 while(!q.empty())
 {
  int o=q.front(); //获得队首元素o
  q.pop();
  int nowp; //当前访问到的边
  for(nowp=f[o];nowp!=0;nowp=next[nowp])
  {
   if(del[nowp]) continue; //此边已经删掉了，则跳过
   if(dist[u[nowp]]+d[nowp]<dist[v[nowp]]) //如果到达边nowp终点的最短路比到达nowp起点最短路和边nowp的权值大，则松弛，将当前边nowp入队
   {
    dist[v[nowp]]=dist[u[nowp]]+d[nowp];
    if(flag) fu[v[nowp]]=nowp; //如果是在跑第一遍SPFA，则记录下当前的点是由哪条边扩展而来
    if(!visit[v[nowp]]) //当前边的起点没有访问过
    {
     q.push(v[nowp]); //将当前边的起点入队
     visit[v[nowp]]=1; //标记当前边的起点访问过
    }
   }
  }
  visit[o]=0; //复原
 }
}
int main()
{
 int i,j,nowp,mint;
 scanf("%d%d",&n,&m);
 for(i=1;i<=m;i++)
 {
  scanf("%d%d%d",&u[i],&v[i],&d[i]);
  next[i]=f[u[i]];
  f[u[i]]=i;
  v[i+m]=u[i]; //无向图,记录完有向边后再记录反向的边
  u[i+m]=v[i];
  d[i+m]=d[i];
  next[i+m]=f[u[i+m]];
  f[u[i+m]]=i+m;
 }
 start=n; //初始时SPFA起点为n
 SPFA();
 flag=0; //第一次spfa结束，标记
 mint=dist[1];
 for(nowp=fu[1];nowp!=0;nowp=fu[u[nowp]]) //寻找最短路上的边，枚举删除一条边，使最终最短路尽可能地大
 {
  del[nowp]=1; //标记此边被删 
  if(nowp<m) del[m-nowp]=1; //反向边也要处理
  else del[nowp-m]=1;
  SPFA();
  del[nowp]=0; //复原 
  if(nowp<m) del[m-nowp]=0;
  else del[nowp-m]=0;
  if(mint<dist[1]&&dist[1]!=INF) //当从起点到终点有路可走，且删除边nowp后的最短路比当前最大最短路大，更新
   mint=dist[1];
 }
 printf("%d\n",mint);
 return 0;
}