CF507E Breaking Good (多关键字最短路 路径还原)

​​linkkk​​​ 题意：
给出一个点边的图，每个边权值都为，表示该边是否能通行，能通行。求从的最短路，要求，最短路长度最短，并且要影响的道路数最少。
影响的道路指的是：如果某条边可以通行但是不在最短路上，破坏这条边；如果某条边不可以通行但是在最短路上，修复这条边。
思路：
第一关键字是长度，第二关键字是最短路上能够通行的路径数。
因为这样破坏和修复的边就较少。维护一个记录路径还原就可以了。
最后答案为最短路径的数量-最短路上工作的路径数量+工作的总道路数-最短路上工作的路径数量。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

typedef pair<int, int>PII;

inline ll read(){ll x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}

inline void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');}



#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)

ll ksm(ll a, ll b,ll mod){ll res = 1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}

#define read read()
#define debug(x) cout<<#x<<":"<<x<<endl;
const int maxn = 5e5 + 7;

struct node{
int v,w,flag;
bool operator < (const node &b)const{return b.w<w;}
};

struct node1{
int u,v,flag;
}edge[maxn];

int n,m,sum,dis[maxn],dp[maxn],pre[maxn];
vector<node>g[maxn];
bool vis[maxn];

void dij(){
memset(dis,0x3f,sizeof dis);
priority_queue<node>q;
q.push({1,0});dis[1]=0;
while(!q.empty()){
node t=q.top();q.pop();
int u=t.v,w=t.w,flag=t.flag;
vis[u]=0;
for(node tt:g[u]){
int v=tt.v,nw=tt.w,nflag=tt.flag;
if(dis[v]>dis[u]+1||(dis[v]==dis[u]+1&&dp[v]<dp[u]+nflag)){
dis[v]=dis[u]+1;
dp[v]=dp[u]+nflag;
pre[v]=u;
if(!vis[v]){
vis[v]=1;
q.push({v,dis[v]});
}
}
}
}
}

int main()
{
n=read,m=read;
rep(i,1,m){
edge[i]={read,read,read};
g[edge[i].u].push_back({edge[i].v,0,edge[i].flag});
g[edge[i].v].push_back({edge[i].u,0,edge[i].flag});
sum=sum+edge[i].flag;///工作的路数
}
dij();
memset(vis,0,sizeof vis);
vis[1]=1;
int ans=dis[n]-dp[n]*2+sum;
//最短路径的数量-最短路上工作的路径数量+工作的总道路数-最短路上工作的路径数量
int x=n;
while(x!=1){
vis[x]=1;
x=pre[x];
}
cout<<ans<<endl;
for(int i=1;i<=m;i++){
int u=edge[i].u,v=edge[i].v,w=edge[i].flag;
if(w){///工作的道路
if(!vis[u]||!vis[v]){//不在最短路径上 炸毁
cout<<u<<" "<<v<<" 0\n";
}
}
else{//不工作的道路
if(vis[u]&&vis[v]){//在最短路径上 修复
cout<<u<<" "<<v<<" 1\n";
}
}
}
return 0;
}