正題

---

題目大意

n個圖，有m條雙向道路，每條道路有一個l和r。
求一條路徑，使得路上最小的r和路上最大的l的差最大。

---

解題思路

我們考慮枚舉l，然后用SPFA計算最大的r。然后這樣會超時。

之后我們發現其實答案的l一定是某一條邊的l，所以我們可以直接枚舉邊的l。

---

code

#include<cstdio> #include<queue> #include<cstring> #include<algorithm> #define N 1010 using namespace std; struct node{int to,l,r,next; }a[N*10]; int n,m,L,R,f[N],ls[N],tot,cnt,lh[N*10]; bool v[N]; queue<int> q; int read(){int x=0,flag=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')flag=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*flag; } void write(int x) {if(x>9) write(x/10);putchar(x%10+48);return; } void addl() {int x,y,l,r;x=read();y=read();l=read();r=read();a[++tot]=(node){y,l,r,ls[x]};ls[x]=tot;a[++tot]=(node){x,l,r,ls[y]};ls[y]=tot; } int spfa(int L) {memset(f,0,sizeof(f));q.push(1);f[1]=2147483647/3;v[1]=true;while(!q.empty()){int x=q.front();q.pop();v[x]=false;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(a[i].l<=L&&a[i].r>=L&&min(a[i].r,f[x])>f[y]){f[y]=min(a[i].r,f[x]);if(!v[y]){v[y]=true;q.push(y);}}}}return f[n]; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){addl();lh[++cnt]=a[tot].l;}sort(lh+1,lh+1+m);cnt=unique(lh+1,lh+1+m)-lh-1;for(int k=1;k<=cnt;k++){int i=lh[k];int r=spfa(i);if(r-i+1>R-L+1){L=i;R=r;}}write(R-L+1);putchar('\n');if(R-L+1)for(int i=L;i<=R;i++)write(i),putchar(' '); } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

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

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