题解 P3753 【国事访问】

· · 题解

在讲题之前，先发一发牢骚：强烈谴责出题人语义不清QAQ！！！

在看到这一道题的一开始，我对照样例和题目看了老久，以为出题人的意思是选择一条最短路，使得除了这条路径上的所有边，这条路上的其他点的其他出边都要被损毁，这样的话就是一个费用计算方式比较与众不同的最小费用最短路，为此我还推了1个小时费用计算公式。满怀信心的交上去，结果......20分?!仅过了样例！！！

把数据点2下下来一看：原来不是路径上的经过点的出边，而是所有非最短路上的边都要求损毁！！！

于是这就变成一个极其容易的最小费用最短路问题了。先把所有未损毁的边的数量统计下来，记一个ans，接着把损毁边(0)的费用设为1（容易理解），把未损毁边(1)的费用设为-1（看下去就理解了），最终答案就是ans+cost[t];

接下来上代码：

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0;
    char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))x=x*10+c-48,c=getchar();
    return x;
}
const int N=1e5+5,INF=1061109567;
struct edge{
    int next,to,opt;
}e[N];
int n,m,tot,ans;
int dis[N],head[N],cost[N];
bool vis[N];
void add(int x,int y,int opt){
    e[++tot]=(edge){head[x],y,opt};
    head[x]=tot;
    e[++tot]=(edge){head[y],x,opt};
    head[y]=tot;
}
void Spfa(){
    memset(dis,0x3f,sizeof(dis));
    memset(cost,0x3f,sizeof(cost));
    queue<int>q;
    q.push(1);
    dis[1]=0;
    vis[n]=true;
    cost[1]=0;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        vis[now]=false;
        for(int i=head[now],nxt;i;i=e[i].next){
            if(dis[nxt=e[i].to]>dis[now]+1){
                dis[nxt]=dis[now]+1;
                if(e[i].opt)cost[nxt]=cost[now]-1;
                else cost[nxt]=cost[now]+1;
                if(!vis[nxt])vis[nxt]=true,q.push(nxt);
            }
            else if(dis[nxt]==dis[now]+1){
                if(e[i].opt){
                    if(cost[nxt]>cost[now]-1){
                        cost[nxt]=cost[now]-1;
                        if(!vis[nxt])vis[nxt]=true,q.push(nxt);
                    }
                }
                else{
                    if(cost[nxt]>cost[now]+1){
                        cost[nxt]=cost[now]+1;
                        if(!vis[nxt])vis[nxt]=true,q.push(nxt);
                    }
                }
            }
        }
    }
}
int main(){
    n=read();m=read();
    int a,b,c;
    for(int i=1;i<=m;++i){
        a=read();b=read();c=read();
        add(a,b,c);
        ans+=c;
    }
    Spfa();
    printf("%d",ans+cost[n]);
    return 0;
}

数据比较水，跑个SPFA只要15ms...