題目鏈接：http://www.lydsy.com/JudgeOnline/problem.php?id=3575
?
大概的做法是，按照順序枚舉每一條要刪去的邊，(假設當前點為$u$，在最短路徑上的下一個點是$v$)然后強制不走${u->v}$這條邊，將$u$入隊，做一遍以$1$號點為原點的SPFA(這個SPFA的dis值是要保留的，因為具有單調性同時也保證了復雜度),如果可以更新到一個最短路徑上的點$x$,顯然就說明在最短路徑$u->x$的所有邊被斷去之后都可以由這條路徑到達匯點，用一個堆維護最小值即可。
注意：SPFA時最短路徑上的點不能入隊。因為某一條邊不走的最短路相當于$1$--沿最短路-->$p1$-->……-->$p2$--沿最短路-->$n$
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<queue> 8 #include<map> 9 #include<cstring> 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 vector<llg>a[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 node&a)const{ 25 return a.val<val; 26 } 27 }; 28 29 priority_queue<node>q; 30 31 void init() 32 { 33 cin>>n>>m>>l; 34 llg x,y,z; 35 for (llg i=1;i<=m;i++) 36 { 37 scanf("%d%d%d",&x,&y,&z); 38 a[x].push_back(y),val[x].push_back(z); 39 e[i].x=x; e[i].y=y; e[i].z=z; 40 } 41 for (llg i=2;i<=n;i++) dis[i]=inf; 42 for (llg i=1;i<=l;i++) 43 { 44 scanf("%d",&sp[i]); 45 pos[e[sp[i]].x]=++posn; 46 } 47 for (llg i=l;i>=1;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,st=x; 54 dl[1]=x; head=0; tail=1; 55 do 56 { 57 head%=SIZE; 58 x=dl[++head]; bj[x]=0; 59 w=a[x].size(); 60 for (llg i=0;i<w;i++) 61 { 62 v=a[x][i]; 63 if (v==V && x==U && Z==val[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.val=dis[v]+dis_T[v]; r.pos=pos[v]; r.wz=v; 76 q.push(r); 77 } 78 } 79 }while (head!=tail); 80 } 81 82 int main() 83 { 84 yyj("road"); 85 init(); 86 for (llg i=1;i<=l;i++) 87 { 88 U=e[sp[i]].x,V=e[sp[i]].y,Z=e[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().pos<=pos[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 }
?
?
.)
