2018年2/3月月赛 Day2 愤怒的瓦里安 题解

发表于 | 分类于

2018年2/3月月赛 Day2 愤怒的瓦里安 题解

题目描述

传奇国王，暴风城主瓦里安·乌瑞恩的儿子安度因又跑到酒馆里和人打牌，还用的是十分肮脏的套牌（脏牧去死啦）。瓦里安听了十分愤怒，掰了筷子就杀了过去。安度因十分慌张，连忙找一起打牌的萨尔帮忙。充满绿色能量的萨尔答应帮安度因破坏一条道路来帮他开溜。但是智商为0的安度因并不知道到底能拖延多长时间。好吧，你写个程序帮他算算咯。（已知萨尔的智商很高，破坏的道路能最大程度上拖延瓦里安的到来）

输入输出格式

输入格式

第一行有两个用空格隔开的数n和m，分别表示道路节点的数量以及道路的数量。道路节点用数字1至n标识，瓦里安的出发地暴风城在节点1，安度因打牌的酒馆在节点n。

接下来的m行中每行包含三个用空格隔开的数u，v和w。这些数字表示在节点u和节点v中间有一条道路，并且花费w的时间通过。

输出格式

输出瓦里安到达酒馆所需要的最短时间。

输入输出样例

输入样例#1： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
10 14
1 2 7
1 9 10
7 9 1
7 3 13
2 3 2
2 4 15
2 8 6
5 9 7
4 8 3
8 5 1
6 8 3
5 6 20
6 10 5
5 10 60

输出样例#1： 

1
74

说明

对于100%的数据，1<=n<=1000，1<=m<=n*(n-1)/2，1<=u,v<=n，1<=w<=1000。

对于本样例，原本走1->2->8->6->10为最短路，时间为21。但萨尔破坏了6->10的路径，使得最短路变为了1->2->8->5->10，时间变为74。可以证明破坏其它道路时所得到的最短路径长度均小于本方案。

通过题意可初步分析为最短路问题的变种，且有明确的起点和终点，又数据较大，故必然使用广搜。

分析题意后可知，可以枚举所有边，逐一删除，再寻找最短路。但边数巨大，逐一枚举必然超时，故采用优化方法：先计算不删边的最短路，并记录该路径，之后枚举该路径上每条边，进行逐一删除，计算，恢复的过程，取最短路最大值即可。此处不证明该算法的正确性。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
int e[1010][1010]={0},ans[1010]={0},v[1010]={0},f[1010]={0},maxn=0,n,m;
queue<int>q;
void bfs()
{
  while(!q.empty()) q.pop();
  memset(v,0,sizeof(v));
  memset(ans,0,sizeof(ans));
  v[1]=1;
  q.push(1);
  while(!q.empty())
  {
      int st=q.front();
      q.pop();
      v[st]=0;
      for(int i=2;i<=n;i++)
      {
          int p=0;
          if(e[st][i]&&(!ans[i]||ans[i]>ans[st]+e[st][i])) ans[i]=ans[st]+e[st][i],p=1;
          if(p&&!v[i]) q.push(i),v[i]=1;
      }
  }
}
int main()
{
  cin>>n>>m;
  for(int i=0;i<m;i++)
  {
      int a,b;
      scanf("%d%d",&a,&b);
      scanf("%d",&e[a][b]);
      e[b][a]=e[a][b];
  }
  v[1]=1;
  q.push(1);
  while(!q.empty())
  {
      int st=q.front();
      q.pop();
      v[st]=0;
      for(int i=2;i<=n;i++)
      {
          int p=0;
          if(e[st][i]&&(!ans[i]||ans[i]>ans[st]+e[st][i])) ans[i]=ans[st]+e[st][i],p=1,f[i]=st;
          if(p&&!v[i]) q.push(i),v[i]=1;
      }
  }
  int t=n,tmp,temp;
  while(t!=1)
  {
      tmp=f[t];
      temp=e[t][tmp];
      e[t][tmp]=e[tmp][t]=0;
      bfs();
      e[t][tmp]=e[tmp][t]=temp;
      if(ans[n]>maxn) maxn=ans[n];
      t=f[t];
  }
  cout<<maxn;
  return 0;
}
--It's the end.Thanks for your read.--