正題

---

大意

一張無向圖，求次短路。

---

解題思路

我們先求出最短路并且求出點1和點n到每個點的距離，然后枚舉邊，將第一個點離點1的距離，和第二個點離點n的距離加上邊權如果不是最短路就記錄，然后取最小值。
IOI賽制不需要證明正確性

---

代碼

#include<cstdio> #include<queue> #include<cstring> #define MN 5010 using namespace std; queue<int> q; struct line{int from,to,w,next; }a[300010]; int n,m,tot,x,y,w,f[MN],ls[MN],len[MN],f2[MN],ans; bool v[MN]; void addl(int x,int y,int w) {a[++tot].from=x;a[tot].to=y;a[tot].w=w;a[tot].next=ls[x];ls[x]=tot; } void spfa() {memset(f,127/3,sizeof(f));q.push(1);v[1]=1;f[1]=0;while (!q.empty()){int x=q.front();q.pop();v[x]=0;for (int i=ls[x];i;i=a[i].next){int y=a[i].to;if (f[x]+a[i].w<f[y]){f[y]=f[x]+a[i].w;if (!v[y]){v[y]=1;q.push(y);}}}} } void spfa1() {memset(f2,127/3,sizeof(f2));q.push(n);v[n]=1;f2[n]=0;while (!q.empty()){int x=q.front();q.pop();v[x]=0;for (int i=ls[x];i;i=a[i].next){int y=a[i].to;if (f2[x]+a[i].w<f2[y]){f2[y]=f2[x]+a[i].w;if (!v[y]){v[y]=1;q.push(y);}}}} } int main() {freopen("block.in","r",stdin);freopen("block.out","w",stdout);scanf("%d%d",&n,&m);for (int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&w);addl(x,y,w);addl(y,x,w);//加邊}spfa();spfa1();//兩遍SPFAint shest=f[n];//記錄最短路ans=2147483647;for (int i=1;i<=tot;i++)if (f[a[i].from]+f2[a[i].to]+a[i].w>shest&&f[a[i].from]+f2[a[i].to]+a[i].w<ans)ans=f[a[i].from]+f2[a[i].to]+a[i].w;//記錄答案printf("%d",ans); }

總結

以上是生活随笔為你收集整理的jzoj1267-路障【最短路,SPFA】的全部內容，希望文章能夠幫你解決所遇到的問題。

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