Debug一下午，没想到把n写成m，出锅了。。。
题意：1-n带权无向图，求删掉一条边使之后的最短路最长，输出这个值并输出删边的方案数
正解：先跑两遍dij，然后把最短路的边标记，考虑最短路1---s------t-----n
存在1----s-----x----y----t----n 删掉s---t（因为还要走最短路），所以要维护s---t的最小值（不经过s---t）
因此可以用线段树，
先bfs求出lr，（x：l=s，r=t ）
把1-----s------x------y------t------n的长度放在线段树上维护
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> #include<queue> using namespace std; #define int long long #define olinr return #define _ 0 #define DB double inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } struct node { node *nxt; int to; int dis; bool vis; node() { nxt=NULL; to=dis=vis=0; } }; struct tree { tree *ls; tree *rs; int l; int r; int dat; tree() { dat=l=r=0; ls=rs=NULL; } }; typedef node* nod; typedef tree* tre; nod head[105050]; int n; int m; int diss[105050]; int dist[105050]; bool vis[105050]; int L[105050]; int R[105050]; int st[105050]; int ans[105050]; int cnt; priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q; queue<int>p; inline void add(int from,int to,int dis) { nod t=new node(); t->to=to; t->dis=dis; t->nxt=head[from]; head[from]=t; } inline void dij(int s,int *dis) { dis[s]=0; q.push(make_pair(dis[s],s)); while(!q.empty()) { int tp=q.top().second; q.pop(); if(vis[tp]) continue; vis[tp]=true; for(nod i=head[tp];i;i=i->nxt) { if(dis[i->to]>dis[tp]+i->dis) { dis[i->to]=dis[tp]+i->dis; q.push(make_pair(dis[i->to],i->to)); } } } memset(vis,0,sizeof vis); } inline void bfs(int s,int *dis,int *X) { p.push(st[s]); X[st[s]]=s; while(!p.empty()) { int tp=p.front(); p.pop(); for(nod i=head[tp];i;i=i->nxt) { if(dis[i->to]==dis[tp]+i->dis&&!X[i->to]&&!vis[i->to]) { p.push(i->to); X[i->to]=s; } } } } inline void build(tre now,int l,int r) { now->l=l; now->r=r; now->dat=0x7fffffff; if(l==r) return; int mid=(l+r)>>1; now->ls=new tree(); now->rs=new tree(); build(now->ls,l,mid); build(now->rs,mid+1,r); } inline void update(tre now,int x,int y,int k) { if(now->l>y||now->r<x) return; if(x<=now->l&&now->r<=y) { now->dat=min(now->dat,k); return; } update(now->ls,x,y,k); update(now->rs,x,y,k); } inline void query(tre now) { if(now->l==now->r) { ans[now->l]=now->dat; return; } now->ls->dat=min(now->ls->dat,now->dat); now->rs->dat=min(now->rs->dat,now->dat); query(now->ls); query(now->rs); } signed main() { n=read(); m=read(); for(int a,b,c,i=1;i<=m;i++) //m写成n，死了一个多小时 { a=read(); b=read(); c=read(); add(a,b,c); add(b,a,c); } memset(diss,0x7f,sizeof diss); memset(dist,0x7f,sizeof dist); dij(1,diss); dij(n,dist); //两遍dij for(int i=1;i!=n;) //标记边 { vis[i]=true; st[++cnt]=i; for(nod now=head[i];now;now=now->nxt) { if(dist[i]==dist[now->to]+now->dis) { now->vis=true; i=now->to; break; } } } st[++cnt]=n; //最短路的点 vis[n]=true; for(int i=1;i<cnt;i++) bfs(i,diss,L); for(int i=cnt;i>=1;i--) //两次bfs（图的联通） bfs(i,dist,R); tre root=new tree(); //我TM就是写指针你咬我。。。。 build(root,1,cnt); //建树 for(int i=1;i<=n;i++) for(nod now=head[i];now!=NULL;now=now->nxt) { if(now->vis) continue; if(L[i]<R[now->to]&&L[i]&&R[now->to]) { update(root,L[i],R[now->to]-1,diss[i]+dist[now->to]+now->dis); //更新线段树 } } query(root);// 求ans int num=0; int maxn=0; for(int i=1;i<cnt;i++) { if(ans[i]>maxn) //累计 { maxn=ans[i]; num=1; } else if(ans[i]==maxn) num++; } if(maxn==diss[n]) num+=m-cnt+1; //刚好是最短路; put(maxn); putchar(' '); put(num); return 0; }