题目链接

题面：

题意：
给定一张n个点m条边的无向图，保证没有自环和重边。
每条边是好边（z=1），或者坏边（z=0）.
现在要求一条从1–n的最短路，在最短路上的坏边要修改成好边，在最短路以外的好边要修改成坏边，这个修改次数为最短路的修改权值。
若有多条最短路，则选择修改权值最小的一条最短路。

修改权值=最短路上的坏边+最短路以外的好边
修改权值=最短路上的边 - 最短路上的好边 + 全图的好边 - 最短路上的好边
修改权值=最短路上的边 + 全图的好边 - 2*最短路上的好边
要想使修改权值最小，那么就需要最短路上的好边最多，用dij求一下，同时维护一个最短路上好边最大值。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<set>
#define ll long long
#define pr make_pair
#define pb push_back
#define ui unsigned int
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define tlen(x) (t[(x)].r-t[(x)].l+1)
#define tmid (l+r)>>1
#define forhead for(int i=head[x];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1000000007;
const double eps=1e-8;
const double pi=acos(-1.0);
const int maxn=200100;
const int maxm=100100;
const int up=100000;

int head[maxn],ver[maxn],edge[maxn],nt[maxn],tot=1;
int x[maxn],y[maxn],z[maxn],d[maxn],pre[maxn],sum[maxn];
bool ha[maxn];

void add(int x,int y,int z=0)
{
    ver[++tot]=y,edge[tot]=z;
    nt[tot]=head[x],head[x]=tot;
}

void dij(int s)
{
    memset(d,0x3f,sizeof(d));
    memset(ha,0,sizeof(ha));
    memset(pre,0,sizeof(pre));
    memset(sum,0,sizeof(sum));
    d[s]=0;
    priority_queue<pair<int,int> >q;
    q.push(pr(0,s));
    while(q.size())
    {
        int x=q.top().second;
        q.pop();
        if(ha[x]) continue;
        ha[x]=true;
        forhead
        {
            int y=ver[i],z=edge[i];
            if(d[y]>d[x]+1)
            {
                d[y]=d[x]+1;
                sum[y]=sum[x]+z;
                pre[y]=x;
                q.push(pr(-d[y],y));
            }
            else if(d[y]==d[x]+1)
            {
                if(sum[y]<sum[x]+z)
                {
                    sum[y]=sum[x]+z;
                    pre[y]=x;
                }
            }
        }
    }
}


int main(void)
{
    int n,m;
    scanf("%d%d",&n,&m);
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x[i],&y[i],&z[i]);
        add(x[i],y[i],z[i]);
        add(y[i],x[i],z[i]);
        ans+=z[i];
    }
    dij(1);
    memset(ha,0,sizeof(ha));
    int xx=n;
    while(xx) ha[xx]=true,xx=pre[xx];
    printf("%d\n",d[n]+ans-2*sum[n]);
    for(int i=1;i<=m;i++)
    {
        if(ha[x[i]]==true&&ha[y[i]]==true&&z[i]==0) printf("%d %d 1\n",x[i],y[i]);
        if((ha[x[i]]==false||ha[y[i]]==false)&&z[i]==1) printf("%d %d 0\n",x[i],y[i]);
    }
    return 0;
}