自动搬运

查看原文

来自洛谷，原作者为

	天南月 又是一个AFO的有害垃圾

搬运于2025-08-24 21:52:21，当前版本为作者最后更新于2019-08-12 22:14:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在讲题之前，先发一发牢骚：强烈谴责出题人语义不清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...