Codeforces507E - Breaking Good （最短路-还原边）

Codeforces507E - Breaking Good （最短路-还原边）

​​题目链接​​

题目描述：

给你n个点m条无向边，每个边有好坏区别（0/1）,边权都为1。 求1-n的路径中 设t1为最短路中的坏路 t2为非最短路中的好路 在保证最短路径的前提下，求t1+t2的最小值

题解：

首先 最短路中我们要尽量保证好边多，所以我们尽可能走好边多的点（在最短路相等的情况下） 然后非最短路中的不用管，肯定也是最优了，因为一条边要么在集合t1要么在集合t2，所以要他对答案的贡献小的话，肯定送去一个 对应的集合

具体操作：

之前做过最短路还原路径是记录的点 还原出一条u-v1-v2-v的一个序列 这个题因为边有好坏之分，而且 有t2,t1两个集合，要识别每个集合中的好边和坏边。 所以我们要直到从1-n经过的哪些编号的边

我们还原点的时候开一个pre数组记录每个点的前驱节点，还原边的话只需要在开一个pre2数组记录走到这个点u的前驱边就ok了

注意存的是双向边

Code：

int n,m,head[maxn],cnt,pre1[maxn],dist[maxn],pre2[maxn],val[maxn],vis[maxn],vi[maxn];struct node { int u,v,w,next,id,pos;} e[maxn];void add(int u,int v,int w,int id) { e[cnt].u=u,e[cnt].v=v,e[cnt].id=id; e[cnt].w=w,e[cnt].next = head[u],head[u]=cnt++;}void Slove() { priority_queue,greater >q; q.push({0,1}),dist[1]=0; while(q.size()) { PII fr= q-(); q.pop(); int dian = fr.second; int dis = fr.first; if(vi[dian]) continue; vi[dian]=1; for(int i=head[dian]; ~i; i=e[i].next) { int v=e[i].v; if(dist[v]>dis+e[i].w) { dist[v]=dis+e[i].w; q.push({dist[v],v}); val[v]=val[dian]+e[i].id; pre1[v] = dian; pre2[v] = i; } else if(dist[v]==dis+e[i].w) { int temp = val[dian] + e[i].id; if(temp>val[v]) { val[v] = temp; pre1[v] = dian ; pre2[v] = i; } } } }}struct Node { int u,v,w; Node() {}; Node(int a,int b,int c) { u=a,v=b,w=c; };};int main() { n=read(),m=read(); mst(head,-1),mst(pre2,-1),mst(pre1,-1); rep(i,0,n+10) dist[i]=inf; for(int i=1 ; i<=m ; i++) { int u,v,id; cin>>u>>v>>id; add(u,v,1,id), add(v,u,1,id); } Slove(); int t=n; while(pre1[t]!=-1) { vis[pre2[t]/2] = 1; t=pre1[t]; } vectorans; for(int i=0 ; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。