[HNOI 2014]道路堵塞

75 阅读 0 评论 50 点赞

我是靠谱客的博主冷静戒指，这篇文章主要介绍[HNOI 2014]道路堵塞，现在分享给大家，希望可以做个参考。

Description

A国有N座城市，依次标为1到N。同时，在这N座城市间有M条单向道路，每条道路的长度是一个正整数。现在，A国交通部指定了一条从城市1到城市N的路径，并且保证这条路径的长度是所有从城市1到城市N的路径中最短的。不幸的是，因为从城市1到城市N旅行的人越来越多，这条由交通部指定的路径经常发生堵塞。现在A国想知道，这条路径中的任意一条道路无法通行时，由城市1到N的最短路径长度是多少。

Input

输入文件第一行是三个用空格分开的正整数N、M和L，分别表示城市数目、单向道路数目和交通部指定的最短路径包含多少条道路。按下来M行，每行三个用空格分开的整数a、b和c，表示存在一条由城市a到城市b的长度为c的单向道路。这M行的行号也是对应道路的编号，即其中第1行对应的道路编号为1，第2行对应的道路编号为2，...，第M行对应的道路编号为M。最后一行为L个用空格分开的整数 sp(1)...，，sp(L)，依次表示从城市1到城市N的由交通部指定的最短路径上的道路的编号。

Output

输出文件包含L行，每行为一个整数，第i行(i=1，2...，，L)的整数表示删去编号为sp(i)的道路后从城市1到城市N的最短路径长度。如果去掉后没有从城市1到城市N的路径，则输出一1。

Sample Input

复制代码

Sample Output

复制代码

Hint

100%的数据满足2<N<100000，1<M<200000。所用道路长度大于0小于10000。

题目大意

给出一个N个节点，M条边的有向图。给出一条1到N的最短路，问最短路上任意一条边断掉，此时的最短路是多少。

题解

考虑不可能每次删掉当前边之后再跑一遍最短路，那必须想办法优化删边和求得最短路过程。

我们将最短路上的点从小到大标号。

考虑删边之后，当前的从$1$到$N$的最短路只能是从$1$出发，在最短路径上走一段，再走一段非最短路，最后回到最短路径上。那么如果强制不走当前边，在跑最短路的过程中，只要发现走到了一个最短路径上的点上时（这个点肯定是最短路上标号更大的点），既然在最短路上，就不必要继续松弛了，显然$SPFA$求出的$dis$值+该点到终点的距离$last$就是一个可行的解，更新$ans$。

其实上述过程得到的解还是没有充分利用的。我们会发现，以后的$SPFA$搜到解会和当前这次$SPFA$得到的解重复。这些重复的解的共同特点就是终止的节点的标号都大于这两个的标号。（想象一下，既然第一次搜到了一个标号很大的解，显然它是没有在这个点之前走上最短路的，就是它同时也绕过了后来的一条强制不走的边），所以这个解是可以继续用的。

用堆保存一下走到哪个在最短路上的点导致的更新$ans$的话，就可以在以后反复调用，保证全局最优了。注意每次跑$SPFA$无需清空$dis$，因为最短路从左往右做的时候，$dis$显然递减（想一想最短路的松弛操作），但是到达最短路上的点的标记必须清空。

玄学的时间复杂度...也能过...人生处处是惊喜...难道不是吗？

$SPFA$的时候不要用$STL$中的$queue$，$n$次拓展慢的吓人<代码中沿用，简洁一些（其实我懒，不想改）>。

复制代码

1 #include<set>

2 #include<map>

3 #include<queue>

4 #include<stack>

5 #include<cmath>

6 #include<ctime>

7 #include<string>

8 #include<cstdio>

9 #include<vector>
 10 #include<cstring>
 11 #include<cstdlib>
 12 #include<iostream>
 13 #include<algorithm>
 14 #define LL long long
 15 #define RE register
 16 #define IL inline
 17
using namespace std;
 18 const int N=100000;
 19 const int M=200000;
 20
 21 IL int Read();
 22
 23 int n,m,l,sp[N+5];
 24 int last[N+5],id[N+5];
 25 struct Link
 26 {
 27
int from,to,cost;
 28 }lin[M+5];
 29 struct tt
 30 {
 31
int to,next,cost,id;
 32 }edge[M+5];
 33 int path[N+5],top;
 34 IL void Add(int u,int v,int c,int id);
 35
 36 struct node
 37 {
 38
int u,dis;
 39
bool operator <
(const node &b)
 40
const{
 41
return dis>b.dis;
 42 
}
 43 };
 44 priority_queue<node>Q;
 45
 46 int dis[N+5];
 47 bool vis[N+5];
 48 IL void SPFA(int donot);
 49
 50 int main()
 51 {
 52
n=Read();m=Read();l=Read();
 53
for (RE int i=1;i<=m;i++)
 54 
{
 55
lin[i].from=Read();lin[i].to=Read();lin[i].cost=Read();
 56
Add(lin[i].from,lin[i].to,lin[i].cost,i);
 57 
}
 58
id[1]=1;
 59
for (RE int i=1;i<=l;i++) sp[i]=Read(),id[lin[sp[i]].to]=id[lin[sp[i]].from]+1;
 60
for (RE int i=l;i;i--) last[lin[sp[i]].from]=last[lin[sp[i]].to]+lin[sp[i]].cost;
 61
memset(dis,127/3,sizeof(dis));dis[1]=0;
 62
for (RE int i=1;i<=l;i++)
 63 
{
 64
if (i>1) dis[lin[sp[i-1]].to]=dis[lin[sp[i-1]].from]+lin[sp[i-1]].cost;
 65 
SPFA(sp[i]);
 66
while (!Q.empty()&&id[lin[sp[i]].from]>=id[Q.top().u]) Q.pop();
 67
printf("%dn",Q.empty() ? -1:Q.top().dis);
 68 
}
 69
return 0;
 70 }
 71
 72 IL void SPFA(int donot)
 73 {
 74
queue<int>q;
 75
while (!q.empty()) q.pop();
 76
q.push(lin[donot].from);
 77
memset(vis,0,sizeof(vis));
 78
while (!q.empty())
 79 
{
 80
for (RE int i=path[q.front()];i;i=edge[i].next) if (edge[i].id!=donot)
 81 
{
 82
if (dis[edge[i].to]>dis[q.front()]+edge[i].cost)
 83 
{
 84
dis[edge[i].to]=dis[q.front()]+edge[i].cost;
 85
if (id[edge[i].to]) Q.push((node){edge[i].to,dis[edge[i].to]+last[edge[i].to]});
 86
else if (!vis[edge[i].to])
 87 
{
 88
vis[edge[i].to]=1;
 89 
q.push(edge[i].to);
 90 
}
 91 
}
 92 
}
 93
vis[q.front()]=0;
 94 
q.pop();
 95 
}
 96 }
 97 IL void Add(int u,int v,int c,int id)
 98 {
 99
edge[++top].to=v;
100
edge[top].cost=c;
101
edge[top].id=id;
102
edge[top].next=path[u];
103
path[u]=top;
104 }
105 IL int Read()
106 {
107
char c=getchar();
108
int sum=0;
109
while (c<'0'||c>'9') c=getchar();
110
while (c>='0'&&c<='9') sum=sum*10+c-'0',c=getchar();
111
return sum;
112 }

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180

1 #include<set>

2 #include<map>

3 #include<queue>

4 #include<stack>

5 #include<cmath>

6 #include<ctime>

7 #include<string>

8 #include<cstdio>

9 #include<vector>
 10 #include<cstring>
 11 #include<cstdlib>
 12 #include<iostream>
 13 #include<algorithm>
 14 #define LL long long
 15 #define RE register
 16 #define IL inline
 17
using namespace std;
 18 const int N=100000;
 19 const int M=200000;
 20
 21 IL int Read();
 22
 23 int n,m,l,sp[N+5];
 24 int last[N+5],id[N+5];
 25 struct Link
 26 {
 27
int from,to,cost;
 28 }lin[M+5];
 29 struct tt
 30 {
 31
int to,next,cost,id;
 32 }edge[M+5];
 33 int path[N+5],top;
 34 IL void Add(int u,int v,int c,int id);
 35
 36 struct node
 37 {
 38
int u,dis;
 39
bool operator <
(const node &b)
 40
const{
 41
return dis>b.dis;
 42 
}
 43 };
 44 priority_queue<node>Q;
 45
 46 int dis[N+5];
 47 bool vis[N+5];
 48 IL void SPFA(int donot);
 49
 50 int main()
 51 {
 52
n=Read();m=Read();l=Read();
 53
for (RE int i=1;i<=m;i++)
 54 
{
 55
lin[i].from=Read();lin[i].to=Read();lin[i].cost=Read();
 56
Add(lin[i].from,lin[i].to,lin[i].cost,i);
 57 
}
 58
id[1]=1;
 59
for (RE int i=1;i<=l;i++) sp[i]=Read(),id[lin[sp[i]].to]=id[lin[sp[i]].from]+1;
 60
for (RE int i=l;i;i--) last[lin[sp[i]].from]=last[lin[sp[i]].to]+lin[sp[i]].cost;
 61
memset(dis,127/3,sizeof(dis));dis[1]=0;
 62
for (RE int i=1;i<=l;i++)
 63 
{
 64
if (i>1) dis[lin[sp[i-1]].to]=dis[lin[sp[i-1]].from]+lin[sp[i-1]].cost;
 65 
SPFA(sp[i]);
 66
while (!Q.empty()&&id[lin[sp[i]].from]>=id[Q.top().u]) Q.pop();
 67
printf("%dn",Q.empty() ? -1:Q.top().dis);
 68 
}
 69
return 0;
 70 }
 71
 72 IL void SPFA(int donot)
 73 {
 74
queue<int>q;
 75
while (!q.empty()) q.pop();
 76
q.push(lin[donot].from);
 77
memset(vis,0,sizeof(vis));
 78
while (!q.empty())
 79 
{
 80
for (RE int i=path[q.front()];i;i=edge[i].next) if (edge[i].id!=donot)
 81 
{
 82
if (dis[edge[i].to]>dis[q.front()]+edge[i].cost)
 83 
{
 84
dis[edge[i].to]=dis[q.front()]+edge[i].cost;
 85
if (id[edge[i].to]) Q.push((node){edge[i].to,dis[edge[i].to]+last[edge[i].to]});
 86
else if (!vis[edge[i].to])
 87 
{
 88
vis[edge[i].to]=1;
 89 
q.push(edge[i].to);
 90 
}
 91 
}
 92 
}
 93
vis[q.front()]=0;
 94 
q.pop();
 95 
}
 96 }
 97 IL void Add(int u,int v,int c,int id)
 98 {
 99
edge[++top].to=v;
100
edge[top].cost=c;
101
edge[top].id=id;
102
edge[top].next=path[u];
103
path[u]=top;
104 }
105 IL int Read()
106 {
107
char c=getchar();
108
int sum=0;
109
while (c<'0'||c>'9') c=getchar();
110
while (c>='0'&&c<='9') sum=sum*10+c-'0',c=getchar();
111
return sum;
112 }