正題

---

大意

有一個大人物，它要從經過一些地方，他所在的路會被封閉（不可以進入，可以出）。你要從一個點到到另一個點，求最短時間。

---

解題思路

求出每條路的封閉時間，然后SPFA

---

代碼

#include<cstdio> #include<cstring> using namespace std; struct line{int x,y,w,next,en,st; }a[20001]; int p[1001],state[1001],f[1001],n,s,e,mn,m,t,g,ww,xx,yy,head,tail,ls[1001]; bool v[1001]; void spfa() {state[1]=s;v[s]=true;memset(f,127/3,sizeof(f));f[s]=t;head=0;tail=1;do{head=head%n+1;int q=ls[state[head]];while (q){if (f[a[q].x]+a[q].w<f[a[q].y] && (f[a[q].x]<a[q].st || f[a[q].x]>=a[q].en))//直接走{f[a[q].y]=f[a[q].x]+a[q].w;if (!v[a[q].y]){tail=tail%n+1;state[tail]=a[q].y;v[a[q].y]=true;}}else if (f[a[q].x]>=a[q].st && f[a[q].x]<a[q].en && a[q].en+a[q].w<f[a[q].y])//等道路開啟{f[a[q].y]=a[q].en+a[q].w;if (!v[a[q].y]){tail=tail%n+1;state[tail]=a[q].y;v[a[q].y]=true;}}q=a[q].next;}v[state[head]]=false;}while (head!=tail); } int main() {scanf("%d%d%d%d%d%d",&n,&mn,&s,&e,&t,&g);for (int i=1;i<=g;i++){scanf("%d",&p[i]);}for (int i=1;i<=mn;i++){scanf("%d%d%d",&xx,&yy,&ww);a[++m].x=xx;a[m].y=yy;a[m].next=ls[xx];a[m].w=ww;ls[xx]=m;a[++m].y=xx;a[m].x=yy;a[m].next=ls[yy];a[m].w=ww;ls[yy]=m;//插入一條邊}ww=0;for (int i=1;i<g;i++){int q=ls[p[i]];while (a[q].y!=p[i+1])q=a[q].next;a[q].st=ww;ww+=a[q].w;a[q].en=ww;q=ls[p[i+1]];while (a[q].y!=p[i])q=a[q].next;a[q].st=ww-a[q].w;a[q].en=ww;//求路什么時間被封閉}spfa();printf("%d",f[e]-t); }

總結

以上是生活随笔為你收集整理的【2018.3.24】模拟赛之六-ssl2550 重要人物【图论，最短路，SPFA】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。