传送门： CodeForces - 450D
题意：有n个城市，1号为首都，给定m条公路和k条铁路，铁路只能从首都到其他点，问在首都到所有点最短路长度不变的情况下最多能删除多少条铁路。
思路：本来做这个题思路不太对，还好有某包巨给我指明了方向，因为我们要用尽可能少的铁路，而且又要求最短路长度不变，自然而然就会想到在松弛方面做文章，我们可以只用公路建图，将所有有铁路的城市标记出来并将dis数组初始化成到该城市最短的那条铁路的长度，然后再将该城市入队（spfa算法），要注意的一点是由于我们建的图中只有公路，因此松弛的式子取大于等于号的时候我们都要将标记取消，最后看一下还剩几个标记就是要留下几条铁路。
蜜汁TLE：上文提到的某包巨用的是裸的spfa，600+ms轻松水过，然而不知为什么我的裸spfa怎么交怎么T45，几乎改的都一样了还是T45，逼不得已用deque优化了一发终于200+ms水过去了。。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> #define MAXN 10005 #define inf 0x3f3f3f3f3f3f3f3f typedef long long ll; using namespace std; int n,m; struct node{ int v,next; ll w; }mp[MAXN*100]; int pre[MAXN*10]; ll dis[MAXN*10]; bool vis[MAXN*10]; int cnt=0; void init() { cnt=0; memset(pre,-1,sizeof(pre)); } void add(int u,int v,int w) { mp[cnt].v=v; mp[cnt].w=w; mp[cnt].next=pre[u]; pre[u]=cnt++; } int book[MAXN*100]; deque<int>q; void spfa(int s,node *ed,int *fa,ll *d) { memset(book,0,sizeof(book)); while(!q.empty()) q.pop_back(); d[s]=0; book[s]=1; q.push_back(s); for(int i=1;i<=n;i++) if(vis[i]) q.push_back(i),book[i]=1; while(!q.empty()) { int u=q.front(); q.pop_front(); book[u]=0; for(int i=fa[u];i!=-1;i=ed[i].next) { int v=ed[i].v; ll w=ed[i].w; if(d[v]>=d[u]+w)vis[v]=0; if(d[v]>d[u]+w) { d[v]=d[u]+w; if(!book[v]) { if(!q.empty()&&dis[v]>dis[q.front()]) q.push_back(v); else q.push_front(v); book[v]=1; } } } } } int main() { int k,a,b; ll c; cin>>n>>m>>k; init(); int ans=0; for(int i=0;i<m;i++) { scanf("%d%d%lld",&a,&b,&c); add(a,b,c); add(b,a,c); } memset(dis,inf,sizeof(dis)); for(int i=0;i<k;i++) { scanf("%d%lld",&a,&c); dis[a]=min(dis[a],c); vis[a]=1; } spfa(1,mp,pre,dis); for(int i=1;i<=n;i++) { if(vis[i]) ans++; } cout<<k-ans; return 0; }spfa不必传递参数的，我传参是因为我直接套的自己原来写好的模板。。
下面是蜜汁无敌TLE的代码：
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> #define MAXN 10005 #define inf 0x3f3f3f3f3f3f3f3f typedef long long ll; using namespace std; int n,m; struct node{ int v,next; ll w; }mp[MAXN*100]; int pre[MAXN*10]; ll dis[MAXN*10]; bool vis[MAXN*10]; int cnt=0; void init() { cnt=0; memset(pre,-1,sizeof(pre)); } void add(int u,int v,int w) { mp[cnt].v=v; mp[cnt].w=w; mp[cnt].next=pre[u]; pre[u]=cnt++; } int book[MAXN*10]; queue<int>q; void spfa(int s) { memset(book,0,sizeof(book)); while(!q.empty()) q.pop(); dis[s]=0; book[s]=1; q.push(s); for(int i=1;i<=n;i++) if(vis[i]) q.push(i),book[i]=1; while(!q.empty()) { int u=q.front(); q.pop(); book[u]=0; for(int i=pre[u];i!=-1;i=mp[i].next) { int v=mp[i].v; ll w=mp[i].w; if(dis[v]>=dis[u]+w) { dis[v]=dis[u]+w; vis[v]=0; if(!book[v]) { q.push(v); book[v]=1; } } } } } int main() { int k,a,b; ll c; cin>>n>>m>>k; init(); int ans=0; for(int i=0;i<m;i++) { scanf("%d%d%lld",&a,&b,&c); add(a,b,c); add(b,a,c); } memset(dis,inf,sizeof(dis)); for(int i=0;i<k;i++) { scanf("%d%lld",&a,&c); dis[a]=min(dis[a],c); vis[a]=1; } spfa(1); for(int i=1;i<=n;i++) { if(vis[i]) ans++; } cout<<k-ans; return 0; } 求各位大佬走过路过的时候帮小的看一下到底为什么会TLE。。
PS：这题dijkstra+堆优化也能轻松水过，不优化就不得而知了。
