Codeforces Round #287 (Div. 二) 507E E. Breaking Good

在一个有n个城市m条边的国家，有一个犯罪团伙。这个犯罪团伙想要抢银行。犯罪团伙基地在城市1，银行在城市n。有个人Walter想要加入这个犯罪团伙，于是为了过的团伙高层的信任，Walter必须担任一项的任务，那就是在基地到银行之间选出一条最短路。这个国家有若干公路在维修，于是你需要将最短路径上的公路修好，为了阻止别的警察追击我方，还必须将所有的不在最短路上的公路炸毁。假如有多条最短路，那么需要选择影响值最小的一条最短路（影响值=需要维修的公路数+需要炸毁的公路数）.

首先我们需要看清楚题意，我们需要在一个图中找到满足条件的一条路径，这里有两个条件，一是最短路，二是影响值最小。那么我们必须要分清哪一个是需要先满足的！从上面加粗字体来看，那么很显然，我们首先需要保证是最短路！（笔主开始没有读清楚题意，并且在没有观察样例的情况下就2B的啪啪啪的开始敲得热火朝天。。T.T，最后发现和样例对不上，观察了样例才发现自己搞这么半天居然题意搞错了！顿时火冒三丈有木有！(╯°Д°)╯︵ ┻━┻（掀！桌！子！）.......咳咳，继续...）审题是非常重要的。那么保证是最短路的话，在同是最短路的情况下再保证影响值最小即可。

那么，我们需要怎么保证影响值最小？影响值=需要维修的公路数+需要炸毁的公路数, 需要维修的公路数=pathlength(路径长度)-workingnum（路径上完好的公路数），需要炸毁的公路=allworkingnum(整个国家完好的公路数)-workingnum（路径上完好的公路数）。

这样一来，影响值=pathlength+allworkingnum-2*workingnum

如此我们要是影响值最小，那么只需要保证选出来的最短路径上的完好的公路最多就行啦~，于是啪啪啪A掉~~~

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define N 100010
using namespace std;
struct edge{
    int u;
    int v;
    int w;
    bool z;
    int next;
}e[N*2];
int last[N];
int d[N];
int s;
int path[N];
int workNum[N];
bool vis[N];
void spfa(int s)
{
    queue<int> q;
    memset(workNum,0,sizeof(workNum));
    memset(d,0x3f,sizeof(d));
    d[s]=0;
    memset(vis,0,sizeof(vis));

    q.push(s);
    vis[s]=1;
    path[s]=-1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int k=last[x];k!=-1;k=e[k].next)
        {
            int u=e[k].u,v=e[k].v;
            int dist=d[u]+e[k].w;
            if(d[v]>dist||(d[v]==dist && workNum[u]+e[k].z>workNum[v]))
            {
                path[v]=u;
                d[v]=dist;
                workNum[v]=workNum[u]+e[k].z;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        memset(last,-1,sizeof(last));
        int eidx=0;
        int workSum=0;
        for(int i=0;i<m;i++)
        {
            int u,v,z;
            scanf("%d%d%d",&u,&v,&z);
            e[eidx].u=u,e[eidx].v=v,e[eidx].z=z,e[eidx].w=1,e[eidx].next=last[u],last[u]=eidx++;
            e[eidx].u=v,e[eidx].v=u,e[eidx].z=z,e[eidx].w=1,e[eidx].next=last[v],last[v]=eidx++;
            workSum+=z;
        }
        spfa(1);
        int ans=d[n]-workNum[n]+workSum-workNum[n];
        cout<<ans<<endl;
        memset(vis,0,sizeof(vis));
        int pre=n;
        while(path[pre]!=-1)
        {
            vis[pre]=1;
            pre=path[pre];
            vis[pre]=1;
        }
        for(int i=0;i<eidx;i+=2)
        {
            int u=e[i].u,v=e[i].v;
            if(e[i].z && !(vis[v] && vis[u]))
                printf("%d %d 0\n",u,v);
            else if((path[v]==u||path[u]==v) && !e[i].z && vis[v] && vis[u])
                printf("%d %d 1\n",u,v);
        }
    }
    return 0;
}