输入一个无向图<V,E> V<=1e5, E<=3e5
现在另外给k条边(u=1,v=s[k],w=y[k])
问在不影响从结点1出发到所有结点的最短路的前提下，最多可以删除k条边的多少条
跑最短路的时候维护或者统计就好了
一开始用spfa.然后TLE 45...好久没写 Dij+堆优化 ...
p.s.优先队列默认大顶堆
Dij+堆优化 264ms
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <string>
using namespace std; #define ll long long
#define maxn 100010
#define maxm 700010 int head[maxn];
struct edge{
int v,w,nxt;
}e[maxm];
int E;
void init(){E=;memset(head,-,sizeof(head));}
void addedge(int u,int v,int w){
e[E].v=v,e[E].w=w,e[E].nxt=head[u];
head[u]=E++;
}
priority_queue<pair<ll,int> >que;
bool vis[maxn];
//ll d[maxn];
int main(){
int n,m,k;
while(~scanf("%d%d%d",&n,&m,&k)){
init();
for(int i=;i<m;++i){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
que.push(make_pair(0ll,));
for(int i=;i<k;++i){
int s,y;
scanf("%d%d",&s,&y);
que.push(make_pair(0ll-y,-s));
}
memset(vis,false,sizeof(vis));
int ans=;
while(!que.empty()){
pair<ll,int> tmp = que.top();que.pop();
ll dis = -tmp.first;
int u = tmp.second;
if(u<){
u=-u;
if(vis[u])++ans;
}
if(vis[u]) continue;
vis[u]=true;
//d[u] = dis;
for(int i=head[u];i!=-;i=e[i].nxt)
if(vis[e[i].v]==false)
que.push(make_pair( -dis-e[i].w, e[i].v));
}
printf("%d\n",ans);
}
return ;
}
spfa TLE 45
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <string>
using namespace std; #define ll long long
#define maxn 100010
#define maxm 700010 int head[maxn];
struct edge{
int v,w,nxt;
int k;
}e[maxm];
int E;
void init(){E=;memset(head,-,sizeof(head));}
void addedge(int u,int v,int w,int kind){
e[E].v=v,e[E].w=w,e[E].nxt=head[u];
e[E].k = kind;
head[u]=E++;
}
int q[maxn];
bool inq[maxn];
bool bus[maxn];
ll dis[maxn];
void spfa(){
int hd=,tl=;
q[tl++]=;
memset(dis,0x3f,sizeof(dis));
dis[]=;
memset(inq,false,sizeof(inq));
inq[]=true;
memset(bus,false,sizeof(bus));
while(hd!=tl){
int u = q[hd++];
if(hd==maxn)hd=;
inq[u] = false;
for(int i=head[u];i!=-;i=e[i].nxt){
int v = e[i].v, w = e[i].w, k = e[i].k;
if(dis[u]+w < dis[v]){
dis[v] = dis[u]+w;
bus[v] = false;
if(k==) bus[v]=true;
if(inq[v]==false){
inq[v]=true;
q[tl++]=v;
if(tl==maxn)tl=;
}
}else if(dis[u]+w == dis[v]){
if(k==) bus[v]=true;
}
}
}
}
int si[],yi[];
int main(){
int n,m,k;
while(~scanf("%d%d%d",&n,&m,&k)){
init();
for(int i=;i<m;++i){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w,);
addedge(v,u,w,);
}
for(int i=;i<k;++i){
scanf("%d%d",si+i,yi+i);
addedge(,si[i],yi[i],);
}
spfa();
int ans=;
for(int i=;i<k;++i){
int v = si[i];
if(dis[v] < yi[i]) ++ans;
else {
if(bus[v]==false)bus[v]=true;
else ++ans;
}
}
printf("%d\n",ans);
}
return ;
}