网站建设数据库放哪,西安网站开发公司有哪家好,百度我的订单查询,如何宣传推广自己的店铺题目链接#xff1a;http://www.lydsy.com/JudgeOnline/problem.php?id3575 大概的做法是#xff0c;按照顺序枚举每一条要删去的边#xff0c;(假设当前点为$u$#xff0c;在最短路径上的下一个点是$v$)然后强制不走${u-v}$这条边#xff0c;将$u$入队#xff0c;做…题目链接http://www.lydsy.com/JudgeOnline/problem.php?id3575 大概的做法是按照顺序枚举每一条要删去的边(假设当前点为$u$在最短路径上的下一个点是$v$)然后强制不走${u-v}$这条边将$u$入队做一遍以$1$号点为原点的SPFA(这个SPFA的dis值是要保留的因为具有单调性同时也保证了复杂度),如果可以更新到一个最短路径上的点$x$,显然就说明在最短路径$u-x$的所有边被断去之后都可以由这条路径到达汇点用一个堆维护最小值即可。 注意SPFA时最短路径上的点不能入队。因为某一条边不走的最短路相当于$1$--沿最短路--$p1$--……--$p2$--沿最短路--$n$ 1 #includeiostream2 #includecstdio3 #includealgorithm4 #includevector5 #includecstdlib6 #includecmath7 #includequeue8 #includemap9 #includecstring
10 using namespace std;
11 #define maxn 1001000
12 #define inf 0x7fffffff
13 #define SIZE 1000000
14 #define llg int
15 #define yyj(a) freopen(a.in,r,stdin),freopen(a.out,w,stdout);
16 llg n,m,posn,pos[maxn],dis[maxn],dl[maxn],head,tail,l,sp[maxn],bj[maxn],U,V,Z,dis_T[maxn];
17 vectorllga[maxn],val[maxn];
18
19 struct Edge{llg x,y,z;}e[maxn];
20
21 struct node
22 {
23 llg pos,val,wz;
24 bool operator(const nodea)const{
25 return a.valval;
26 }
27 };
28
29 priority_queuenodeq;
30
31 void init()
32 {
33 cinnml;
34 llg x,y,z;
35 for (llg i1;im;i)
36 {
37 scanf(%d%d%d,x,y,z);
38 a[x].push_back(y),val[x].push_back(z);
39 e[i].xx; e[i].yy; e[i].zz;
40 }
41 for (llg i2;in;i) dis[i]inf;
42 for (llg i1;il;i)
43 {
44 scanf(%d,sp[i]);
45 pos[e[sp[i]].x]posn;
46 }
47 for (llg il;i1;i--) dis_T[e[sp[i]].x]dis_T[e[sp[i]].y]e[sp[i]].z;
48 pos[n]posn;
49 }
50
51 void spfa(llg x)
52 {
53 llg v,w,stx;
54 dl[1]x; head0; tail1;
55 do
56 {
57 head%SIZE;
58 xdl[head]; bj[x]0;
59 wa[x].size();
60 for (llg i0;iw;i)
61 {
62 va[x][i];
63 if (vV xU Zval[x][i]) continue;
64 if (dis[v]dis[x]val[x][i]) continue;
65 dis[v]dis[x]val[x][i];
66 if (!bj[v] !pos[v])
67 {
68 bj[v]1;
69 tail%SIZE; dl[tail]v;
70 }
71 if (pos[v])
72 {
73 if (pos[v]pos[st]) continue;
74 node r;
75 r.valdis[v]dis_T[v]; r.pospos[v]; r.wzv;
76 q.push(r);
77 }
78 }
79 }while (head!tail);
80 }
81
82 int main()
83 {
84 yyj(road);
85 init();
86 for (llg i1;il;i)
87 {
88 Ue[sp[i]].x,Ve[sp[i]].y,Ze[sp[i]].z;
89 if (i!1) dis[e[sp[i]].x]dis[e[sp[i-1]].x]e[sp[i-1]].z;
90 spfa(e[sp[i]].x);
91 while (!q.empty())
92 {
93 if (q.top().pospos[e[sp[i]].x]) q.pop();else break;
94 }
95 if (q.empty()) puts(-1);else printf(%d\n,q.top().val);
96 }
97 return 0;
98 } 转载于:https://www.cnblogs.com/Dragon-Light/p/6430742.html
