linkkk
题意：
给出一个n点m边的图，每个边权值都为1，f l a g表示该边是否能通行，能通行f a g = = 1。求从1 − n的最短路，要求，最短路长度最短，并且要影响的道路数最少。
影响的道路指的是：如果某条边可以通行但是不在最短路上，破坏这条边；如果某条边不可以通行但是在最短路上，修复这条边。
思路：
第一关键字是长度，第二关键字是最短路上能够通行的路径数。
因为这样破坏和修复的边就较少。维护一个p r e记录路径还原就可以了。
最后答案为最短路径的数量-最短路上工作的路径数量+工作的总道路数-最短路上工作的路径数量。
代码：
#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; }
