洛谷 [P3110] 驮运

题目略带一点贪心的思想，先跑三遍最短路（边权为一，BFS比SPFA高效）

一起跑总比分开跑高效，枚举两人在何点汇合，输出最小值。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cstring>

#include <queue>

using namespace std;

const int MAXN=40005;

int head[MAXN],nume,p,w,n,m,b,tot=0x7fffffff/3;

struct edge{

	int to,nxt;

}e[MAXN*2];

int dis[MAXN][4],wei[4];

bool f[MAXN];

int read(){

	int rv=0,fh=1;

	char c=getchar();

	while(c<'0'||c>'9'){

		if(c=='-') fh=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9'){

		rv=(rv<<1)+(rv<<3)+c-'0';

		c=getchar();

	}

	return fh*rv;

}

void adde(int from,int to){

	e[++nume].to=to;

	e[nume].nxt=head[from];

	head[from]=nume;

}

void spfa(int x){

	memset(f,0,sizeof(f));

	for(int i=1;i<=n;i++){

		dis[i][x]=0x7fffffff/3;

	}

	queue<int> q;

	if(x==3) {

		dis[n][x]=0;

		q.push(n);

		f[n]=1;

	}else {dis[x][x]=0;q.push(x);f[x]=1;}

	while(!q.empty()){

		int u=q.front();

		q.pop();

		f[u]=0;

		for(int i=head[u];i;i=e[i].nxt){

			int v=e[i].to;

			if(dis[v][x]>dis[u][x]+wei[x]){

				dis[v][x]=dis[u][x]+wei[x];

					if(!f[v]){

						q.push(v);

						f[v]=1;

				}

			}

		}

	}

}

int main(){

	freopen("in.txt","r",stdin);

	b=read();w=read();p=read();n=read();m=read();

	for(int i=1;i<=m;i++){

		int u=read(),v=read();

		adde(u,v);adde(v,u);

	}

	wei[1]=b;wei[2]=w;wei[3]=p;

	spfa(1);spfa(2);spfa(3);

	for(int i=1;i<=n;i++){

		int sum=dis[i][1]+dis[i][2]+dis[i][3];

		tot=min(sum,tot);

	}

	cout<<tot;

	fclose(stdin);

	return 0;

}

巴特西

洛谷 [P3110] 驮运

最新文章

热门文章