Codeforces Round #257 div.2 D or 450D Jzzhu and Cities【最短路】
题目链接：点击打开
题目大意： 在一个国家中有n个城市（城市编号1~n），m条公路和k条铁路，编号为1的城市为首都，为了节约，不需要的铁路需要关闭，问在保证首都到其余所有城市的最短路不变的条件下，最多有多少条铁路是不需要的。
解法： 这个题比较麻烦，保证首都到其余城市的最短路不变，要求出最多有多少条铁路是不需要的，那肯定是从最短路的代码上下手了，我们首先考虑dijkstra算法，假设此时我们处理的图没有重边。
让我百思不得其解的是，我写完此题submit之后居然给我返回了一个MLE！让我想半天想不通，CF服务器内存限制一直是256MB,很少出现这种情况，也不可能是数组太大的缘故，我想了很久，突然想到很有可能是dijkstra算法中的优先队列存的数据太多导致的内存超出限制，于是赶紧加了一条限制。果然就过了。
//MLE code(松弛部分): if(d[v]>d[u]+w || (d[v]==d[u]+w && !is)) { path[v]=u; d[v]=d[u]+w; que.push(PII(d[v],v)); } //AC code(松弛部分): if(d[v]>d[u]+w || (d[v]==d[u]+w && !is && trainofpath[v])) { trainofpath[v]=is; path[v]=u; d[v]=d[u]+w; que.push(PII(d[v],v)); } 这里采用了一个布尔数组trainofpath[v]记录到v点的这条边是不是铁路。如果这条路原本是铁路，现在更新的是公路，，才进行更新；想上一份MLE的代码如果只要当前更新的是公路就进行操作的话，一些变态的数据会使得压入优先队列中的数据过多，导致MLE。 完整代码如下： ;INF=0x7fffffffffffffffL;struct edge{long long u,v,w,nxt;bool istrain;bool operator< (const edge& o) const{return u<o.u||(u==o.u && v<o.v)||(u==o.u && v==o.v && w<o.w)||(u==o.u && v==o.v && w==o.w && istrain<o.istrain);}}e1[N*4],e[N*3];long long last[N];> PII;long long V;long long d[N];long long path[N];bool trainofpath[N];priority_queue<PII,vector<PII>,greater<PII> > que;void dijkstra(long long s){//memset(d,0x3f,sizeof(d));fill(d+1,d+V+1,INF);d[s]=0;que.push(PII(0,s));while(!que.empty()){PII pp=que.top();que.pop();long long u=pp.second;if(d[u]<pp.first) continue;for(long long i=last[u];i!=-1;i=e[i].nxt){long long v=e[i].v,w=e[i].w;bool is=e[i].istrain;if(d[v]>d[u]+w || (d[v]==d[u]+w && !is && trainofpath[v])){trainofpath[v]=is;path[v]=u;d[v]=d[u]+w;que.push(PII(d[v],v));}}}}int main(){long long n,m,k;scanf(“%I64d%I64d%I64d”,&n,&m,&k);V=n;long long ans=0;memset(last,-1,sizeof(last));for(int i=0;i<=n;i++){trainofpath[i]=true;}for(long long i=0;i<m;i++){long long u,v,w;scanf(“%I64d%I64d%I64d”,&u,&v,&w);if(u>v) swap(u,v);e1[i].u=u,e1[i].v=v,e1[i].w=w,e1[i].istrain=false;}for(long long i=0;i<k;i++){long long v,w;scanf(“%I64d%I64d”,&v,&w);e1[i+m].u=1,e1[i+m].v=v,e1[i+m].w=w,e1[i+m].istrain=true;}sort(e1,e1+m+k);long long edge1Num=1;for(long long i=1;i<m+k;i++){if(e1[i].u==e1[i-1].u && e1[i].v==e1[i-1].v){if(e1[i].istrain) ans++;continue;}e1[edge1Num++]=e1[i];}long long edgeNum=0;for(long long i=0;i<edge1Num;i++){long long u=e1[i].u,v=e1[i].v,w=e1[i].w;bool is=e1[i].istrain;e[edgeNum].u=u,e[edgeNum].v=v,e[edgeNum].w=w,e[edgeNum].istrain=is,e[edgeNum].nxt=last[u],last[u]=edgeNum++;e[edgeNum].v=u,e[edgeNum].u=v,e[edgeNum].w=w,e[edgeNum].istrain=is,e[edgeNum].nxt=last[v],last[v]=edgeNum++;}dijkstra(1);for(long long i=0;i<edgeNum;i+=2){long long u=e[i].u,v=e[i].v;bool is=e[i].istrain;if(!is) continue;if(path[v]==u || path[u]==v) continue;ans++;}cout<<ans<<endl;return 0;}
（这次试了一下新功能Markdown编辑器^_^不怎么会用，看起来比较丑，不过代码显示好像没有以前的漂亮…..可能还需要学习一下新的姿势，嘿嘿）
梦想让我与众不同，奋斗让我改变命运！
