此博客停更

-->http://qiancl.is-programmer.com/user_files/qiancl/Image/Problem%204289.%20--%20PA2012%20Tax.html

PA的题短小精悍-。-

考虑每条边建立一个点，边与边的转移可以通过枚举中间点，把与中间点有关的边暴力抠出来排序，从小到大加，从以中间点为终点的向以x点为起点的连边，边权为原边权，再连向下一条，边权是与上一条的差，再与上一条连边权为0的边，图构好后，直接跑最短路就行了

#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define ll long long
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 200010
#define pk push_back
const ll inf=1ll<<60;queue<int>q;bool vis[N<<1];
int i,j,k,m,n,x,y,z,cnt,last[N<<1];ll dis[N<<1];
struct node{int u,v,w;bool operator <(const node&b)const{return w<b.w;}};
struct edge{int to,next,v;}e[N*6];
#define add(u,v,w) (e[++cnt]=(edge){v,last[u],w},last[u]=cnt)
vector<node>E[N<<1];
int main(){
	for(n=read(),m=read(),i=2;i<=m+1;++i){
		x=read(),y=read(),z=read();
		E[x].pk((node){i<<1,(i<<1)-1,z}),E[y].pk((node){(i<<1)-1,i<<1,z});
		if(x==1)add(1,(i<<1)-1,z);if(y==1)add(1,i<<1,z);
		if(y==n)add((i<<1)-1,2,z);if(x==n)add(i<<1,2,z);
	}
	for(i=1;i<=n;++i){
		int len=E[i].size();sort(E[i].begin(),E[i].end());
		for(j=0;j<len;++j)add(E[i][j].u,E[i][j].v,E[i][j].w);
		for(j=0;j<len-1;++j)add(E[i][j].v,E[i][j+1].v,E[i][j+1].w-E[i][j].w),add(E[i][j+1].v,E[i][j].v,0);
	}
	for(i=2;i<=m+1<<1;++i)dis[i]=inf;q.push(1);
	while(!q.empty()){
		int k=q.front();q.pop(),vis[k]=1;
		for(int i=last[k],y;i;i=e[i].next)if(dis[y=e[i].to]>dis[k]+e[i].v){
			dis[y]=dis[k]+e[i].v;
			if(!vis[y])vis[y]=1,q.push(y);
		}vis[k]=0;
	}
	printf("%lld\n",dis[2]);
}

#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define ll long long
#define nc() getchar()
typedef pair<int,ll>P;
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 200010
#define pk push_back
const ll inf=1ll<<60;priority_queue<P,vector<P>,greater<P> >q;
int i,j,k,m,n,x,y,z,l,r,cnt,last[N<<1];ll dis[N<<1];
struct node{int u,v,w;bool operator <(const node&b)const{return w<b.w;}};
struct edge{int to,next,v;}e[N*6];
#define add(u,v,w) (e[++cnt]=(edge){v,last[u],w},last[u]=cnt)
vector<node>E[N<<1];
int main(){
	for(n=read(),m=read(),i=2;i<=m+1;++i){
		x=read(),y=read(),z=read(),l=i<<1,r=(i<<1)-1;
		E[x].pk((node){l,r,z}),E[y].pk((node){r,l,z});
		if(x==1)add(1,r,z);if(y==1)add(1,l,z);
		if(y==n)add(r,2,z);if(x==n)add(l,2,z);
	}
	for(i=1;i<=n;++i){
		int len=E[i].size();sort(E[i].begin(),E[i].end());
		for(j=0;j<len;++j)add(E[i][j].u,E[i][j].v,E[i][j].w);
		for(j=0;j<len-1;++j)add(E[i][j].v,E[i][j+1].v,E[i][j+1].w-E[i][j].w),add(E[i][j+1].v,E[i][j].v,0);
	}
	for(j=m+1<<1,i=2;i<=j;++i)dis[i]=inf;q.push(P(0,1));
	while(!q.empty()){
		P k=q.top();q.pop();
		if(dis[x=k.second]<k.first)continue;
		for(int i=last[x],y;i;i=e[i].next)if(dis[y=e[i].to]>dis[x]+e[i].v)q.push(P(dis[y]=dis[x]+e[i].v,y));
	}
	printf("%lld\n",dis[2]);
}

loading...